Pagini recente » Cod sursa (job #549392) | Cod sursa (job #910449) | Cod sursa (job #128627) | Cod sursa (job #906071) | Cod sursa (job #290201)
Cod sursa(job #290201)
#include<fstream.h>
#include<string.h>
char A[2000002],B[2000002];
int pi[2000002],p[1001],m,n,q,i,nr;
void cpi()
{int k=0;
for(q=2;q<=m;++q)
{while(k>0&&A[k+1]!=A[q])
k=pi[k];
if(A[k+1]==A[q])
++k;
pi[q]=k;
}
}
int main()
{ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.get(A,2000002);f.get();
f.get(B,2000002);
m=strlen(A);
n=strlen(B);
for(i=m;i;--i)A[i]=A[i-1];
for(i=n;i;--i)B[i]=B[i-1];
cpi();
q=0;
for(i=1;i<=n;++i)
{while(q>0&&A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
++q;
if(q==m)
{q=pi[q];
++nr;
if(nr<1001)
p[nr]=i-m;
}
}
g<<nr<<"\n";
if(nr>1000)nr=1000;
for(i=1;i<=nr;++i)
g<<p[i]<<' ';
return 0;
}