QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#128731 | #552. 字符串匹配问题 | SoyTony# | 0 | 3ms | 11884kb | C++14 | 2.9kb | 2023-07-21 15:17:58 | 2023-07-21 15:33:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=(1<<20)+10;
const int mod=998244353;
const int base1=19260817;
const int base2=993244853;
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int rev[maxn];
int base,w[maxn];
struct Poly{
const static int g=3;
const static int inv_g=332748118;
int deg;
vector<int> f;
int& operator[](const int& i){return f[i];}
int operator[](const int& i)const{return f[i];}
inline void set(int L){deg=L;f.resize(L);}
inline void clear(int L,int R){for(int i=L;i<=R;++i)f[i]=0;}
inline void output(int L){for(int i=0;i<L;++i)printf("%d ",f[i]);printf("\n");}
inline void NTT(int L,bool type){
for(int i=1;i<L;++i){
rev[i]=(rev[i>>1]>>1)+(i&1?L>>1:0);
if(i<rev[i]) swap(f[i],f[rev[i]]);
}
for(int d=1;d<L;d<<=1){
base=q_pow(type?g:inv_g,(mod-1)/(2*d),mod);
w[0]=1;
for(int i=1;i<d;++i) w[i]=1ll*w[i-1]*base%mod;
for(int i=0;i<L;i+=d<<1){
for(int j=0;j<d;++j){
int x=f[i+j],y=1ll*w[j]*f[i+d+j]%mod;
f[i+j]=(x+y)%mod,f[i+d+j]=(x-y+mod)%mod;
}
}
}
if(!type){
int inv_L=q_pow(L,mod-2,mod);
for(int i=0;i<L;++i) f[i]=1ll*f[i]*inv_L%mod;
}
}
}F,G,H;
int n,m;
char s[maxn],t[maxn];
int pw1[27],pw2[27];
int ans1[maxn],ans2[maxn],ans[maxn];
int cnt;
int main(){
scanf("%s",t);
scanf("%s",s);
m=strlen(t+1),n=strlen(s+1);
for(int i=0;i<m;++i){
if(i<m-1-i) swap(t[i],t[m-1-i]);
}
int L=1;
while(L<n+m) L<<=1;
pw1[0]=1,pw2[0]=1;
for(int i=1;i<26;++i) pw1[i]=1ll*pw1[i-1]*base1%mod,pw2[i]=1ll*pw2[i-1]*base2%mod;
F.set(L),G.set(L),H.set(L);
for(int i=0;i<n;++i) F[i]=(s[i]!='*');
for(int i=0;i<m;++i) G[i]=(t[i]!='*');
F.NTT(L,1),G.NTT(L,1);
for(int i=0;i<L;++i) H[i]=1ll*F[i]*G[i]%mod;
H.NTT(L,0);
for(int i=1;i+m-1<=n;++i){
ans1[i]=1ll*H[i-1+m-1]*pw1[25]%mod;
ans2[i]=1ll*H[i-1+m-1]*pw2[25]%mod;
ans[i]=1;
}
F.clear(0,L-1),G.clear(0,L-1);
for(int i=0;i<n;++i) F[i]=(s[i]!='*')?pw2[s[i]-'a']:0;
for(int i=0;i<m;++i) G[i]=(t[i]!='*')?pw2[25-(t[i]-'a')]:0;
F.NTT(L,1),G.NTT(L,1);
for(int i=0;i<L;++i) H[i]=1ll*F[i]*G[i]%mod;
H.NTT(L,0);
for(int i=1;i+m-1<=n;++i){
ans[i]&=(H[i-1+m-1]==ans2[i]);
cnt+=ans[i];
}
if(cnt){
for(int i=1;i+m-1<=n;++i){
if(ans[i]) printf("%d ",i);
}
printf("\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 20
Accepted
time: 3ms
memory: 11884kb
input:
cabacacccbacccaabacacaabcabbabcaccbcabbacbcb aaaccabacaaabb*abaaaa*bcabacacccba*ccaabacadaabcabba*kac*b*abbacabacacccbacccaa*acacaabcabbabca***cabbacbcbcabbacbcbbccbcacbaccbacaacc***bbbabccc**bbcbaaaaaabaabaacbc*cbcca*ccbabbacb*caaabcaba*acccbacccaabcabadac*cbacccaabacacaabca**abcucc*cxbbacb*bbacacc...
output:
64 255 424 477 591 685 794
result:
ok 7 numbers
Test #2:
score: -20
Wrong Answer
time: 3ms
memory: 11860kb
input:
caacacbabcbbbbaccbabcba b*b*aabcaaccya**cbabcbbo**ccbabcb*b*aacacbabaca*c*abcacacaacacba*cbbbbaccba*c*caacacbabcbbbbaccbabcbaacbabcbbbb*ccbabc*abacbcbbbaaaaccaa*acbbaacacc*ac*cb*bcbb*baccbabcbaabcbaaaabccsaabacab**aac*bacbaacaacacba**bbb*ncc*abxbabbbca*cacbabc*bbbaccbabcbabbb*abaccbcccbc**bccbb***cc...
output:
57 79 147 227 339 432 644 696 743 905 928
result:
wrong answer 1st numbers differ - expected: '79', found: '57'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%