Pagini recente » Cod sursa (job #2086751) | Autentificare | Cod sursa (job #1995556) | Cod sursa (job #2005648) | Cod sursa (job #293374)
Cod sursa(job #293374)
#include<fstream>
#include<string.h>
using namespace std;
char a[2000010],b[2000010];
int n,m,i,q,pi[2000010],sol,v[2000010],k;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.get(a+1,2000005); f.get();
f.get(b+1,2000005);
a[0]=b[0]='a';
n=strlen(a)-1;
k=0; pi[1]=0;
for(i=2;i<=n;i++)
{ while ( (k>0) && (a[k+1]!=a[i]) )
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;
}
m=strlen(b)-1;
q=0;
for(i=1;i<=m;i++)
{ while( (q>0) && (a[q+1]!=b[i]) )
q=pi[q];
if(a[q+1]==b[i])
q++;
if(q==n) v[++sol]=i-n;
}
g<<sol<<'\n';
if(sol>1000) sol=1000;
for(i=1;i<=sol;i++) g<<v[i]<<" ";
f.close();
g.close();
return 0;
}