Pagini recente » Cod sursa (job #2949189) | Cod sursa (job #1343936) | Cod sursa (job #2064864) | Cod sursa (job #848339) | Cod sursa (job #2038418)
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
char N[2000000],H[2000000],c;
int h,n,S[2000000],aux[2000000];
int f,k,cont;
ifstream fi("strmatch.in");
ofstream g("strmatch.out");
int main()
{
fi>>N+1>>H+1;
n=strlen(N+1);
h=strlen(H+1);
S[0]=-1;
S[1]=0;
for(int i=2;i<=n;i++){
k=i-1;
c=N[i];
while(S[k]!=-1 && N[S[k]+1]!=c)
k=S[k];
S[i]=S[k]+1;
}
for(int i=1;i<=h;i++){
while(f!=-1)
if(N[f+1] == H[i])
break;
else f=S[f];
if(f==-1)
f=0;
else {
f++;
if(f==n){
cont++;
aux[cont]=i-f;
f=S[f];
}
}
}
g<<cont<<"\n";
for(int i=1;i<=cont && i<=1000;i++)
g<<aux[i]<<" ";
return 0;
}