QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#479454 | #552. 字符串匹配问题 | templatetemplate# | 0 | 18ms | 74316kb | C++17 | 2.5kb | 2024-07-15 17:40:59 | 2024-07-15 17:41:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x){
x=0;
bool flag=0;
char ch=getchar();
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
x=flag?-x:x;
}
template<typename T,typename ...Args>inline void read(T &x,Args &...args){
read(x),read(args...);
}
template<typename T>inline void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
put(x),putchar(ch);
}
template<typename T,typename ...Args>inline void put(char ch,T x,Args ...args){
put(ch,x),put(ch,args...);
}
#define N 1100005
#define ld long double
const ld pi=acos(-1);
struct Complex{
ld x,y;
Complex(ld _x=0,ld _y=0):x(_x),y(_y){}
inline Complex operator+(const Complex &b)const{return Complex(x+b.x,y+b.y);}
inline Complex operator-(const Complex &b)const{return Complex(x-b.x,y-b.y);}
inline Complex operator*(const Complex &b)const{return Complex(x*b.x-y*b.y,x*b.y+y*b.x);}
}f[N],g[N];
int rev[N];
inline void FFT(Complex *c,int len,int typ=1){
for(int i=0;i<len;i++)
if(i>rev[i]) swap(c[i],c[rev[i]]);
for(int arc=1;arc<len;arc<<=1){
Complex base=Complex(cos(typ*pi/arc),sin(typ*pi/arc));
for(int i=0;i<len;i+=arc+arc){
Complex now=Complex(1,0);
for(int j=0;j<arc;j++,now=now*base){
Complex x=c[i+j],y=c[i+j+arc]*now;
c[i+j]=x+y,c[i+j+arc]=x-y;
}
}
}
if(typ==-1){
for(int i=0;i<len;i++) c[i].x/=len;
}
}
long long val[N];
int n,m,a[N],b[N];
char s[N],t[N];
int main(){
scanf("%s%s",s,t),n=strlen(s)-1,m=strlen(t)-1;
for(int i=0;i<=n;i++) a[i]=s[i]=='*'?0:s[i]-'a'+1;
for(int i=0;i<=m;i++) b[i]=t[i]=='*'?0:t[i]-'a'+1;
reverse(a,a+n+1);
int len=1,bit=0;
while(len<=n+m+1) len<<=1,bit++;
for(int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|(i&1)<<(bit-1);
for(int i=0;i<len;i++) f[i]=g[i]=Complex();
for(int i=0;i<=n;i++) f[i].x=a[i]*a[i];
for(int i=0;i<=m;i++) g[i].x=b[i];
FFT(f,len),FFT(g,len);
for(int i=0;i<len;i++) f[i]=f[i]*g[i];
FFT(f,len,-1);
for(int i=0;i<=m;i++) val[i]+=(long long)(f[n+i].x+0.5);
for(int i=0;i<len;i++) f[i]=g[i]=Complex();
for(int i=0;i<=n;i++) f[i].x=a[i];
for(int i=0;i<=m;i++) g[i].x=b[i]*b[i];
FFT(f,len),FFT(g,len);
for(int i=0;i<len;i++) f[i]=f[i]*g[i];
FFT(f,len,-1);
for(int i=0;i<=m;i++) val[i]-=(long long)(f[n+i].x+0.5);
for(int i=0;i<=m-n;i++)
if(!val[i]) put(' ',i+1);
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 18ms
memory: 74316kb
input:
cabacacccbacccaabacacaabcabbabcaccbcabbacbcb aaaccabacaaabb*abaaaa*bcabacacccba*ccaabacadaabcabba*kac*b*abbacabacacccbacccaa*acacaabcabbabca***cabbacbcbcabbacbcbbccbcacbaccbacaacc***bbbabccc**bbcbaaaaaabaabaacbc*cbcca*ccbabbacb*caaabcaba*acccbacccaabcabadac*cbacccaabacacaabca**abcucc*cxbbacb*bbacacc...
output:
56 64 65 80 84 141 164 166 255 258 418 423 424 426 444 450 451 453 477 487 494 495 506 591 607 685 702 792 794 817 825 844 870 910
result:
wrong answer 1st numbers differ - expected: '64', found: '56'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%