QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#125881 | #552. 字符串匹配问题 | cp152# | 0 | 0ms | 0kb | C++14 | 1.6kb | 2023-07-17 20:46:40 | 2023-07-17 20:46:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int M=1048576;
unsigned seed=186164;
unsigned long long rnd()
{
seed^=seed<<7;
seed^=seed>>11;
seed^=seed<<17;
return seed;
}
char c[M+5],d[M+5];
int f[M+5],g[M+5];
int f2[M+5],g2[M+5];
int f3[M+5],g3[M+5];
int hsh[26];
int n,m;
const int mod=998244353,inv3=332748118;
int tr[M+5];
int pw(int a,int b=mod-2)
{
int re=1;
while(b)
{
if(b&1) re=1ll*re*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return re;
}
void NTT(int f[],int len,bool b)
{
for(int i=1;i<len;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?(len>>1):0);
for(int i=0;i<len;i++) if(tr[i]<i) swap(f[i],f[tr[i]]);
for(int i=1;i<len;i*=2)
for(int j=0;j<len;j+=2*i)
{
int yg=pw(b?3:inv3,mod/i/2),dwg=1;
for(int k=0;k<i;k++)
{
int tmp=f[j+k];
f[j+k]=(f[j+k]+1ll*f[i+j+k]*dwg)%mod;
f[i+j+k]=(tmp-1ll*f[i+j+k]*dwg)%mod;
dwg=1ll*dwg*yg%mod;
}
}
if(b)
{
int tmp=pw(len);
for(int i=0;i<len;i++) f[i]=1ll*f[i]*tmp%mod;
}
}
int main()
{
for(int i=0;i<26;i++) hsh[i]=rnd()%mod;
scanf("%s",c);
scanf("%s",d);
for(n=0;c[n];n++);
for(m=0;d[m];m++);
for(int i=n-1;~i;i--) f[n-1-i]=(c[i]=='*'?0:hsh[c[i]-'a']);
for(int i=0;i<m;i++) g[i]=(d[i]=='*'?0:hsh[d[i]-'a']);
for(int i=0;i<n;i++) f2[i]=1ll*f[i]*f[i]%mod,f3[i]=1ll*f2[i]*f[i]%mod;
for(int i=0;i<m;i++) g2[i]=1ll*g[i]*g[i]%mod,g3[i]=1ll*g2[i]*g[i]%mod;
NTT(f,M,0);
NTT(g,M,0);
NTT(f2,M,0);
NTT(g2,M,0);
NTT(f3,M,0);
NTT(g3,M,0);
for(int i=0;i<M;i++) f[i]=(1ll*f[i]*g3[i]-2ll*f2[i]*g2[i]+1ll*f3[i]*g[i])%mod;
NTT(f,M,1);
for(int i=n-1;i<m;i++)
{
if(!f[i]) cout<<i-n+2<<' ';
}
return 0;
}
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
cabacacccbacccaabacacaabcabbabcaccbcabbacbcb aaaccabacaaabb*abaaaa*bcabacacccba*ccaabacadaabcabba*kac*b*abbacabacacccbacccaa*acacaabcabbabca***cabbacbcbcabbacbcbbccbcacbaccbacaacc***bbbabccc**bbcbaaaaaabaabaacbc*cbcca*ccbabbacb*caaabcaba*acccbacccaabcabadac*cbacccaabacacaabca**abcucc*cxbbacb*bbacacc...
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%