Pagini recente » Cod sursa (job #1728332) | Cod sursa (job #1806559) | Cod sursa (job #1369281) | Cod sursa (job #2138247) | Cod sursa (job #293798)
Cod sursa(job #293798)
#include<fstream>
#include<string.h>
using namespace std;
char a[2000010],b[2000010];
int n,m,i,q,pi[2000010],sol,v[1010],k;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.get(a+1,2000005); f.get();
f.get(b+1,2000005);
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) { sol++; if(sol<=100) 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;
}