Pagini recente » Cod sursa (job #2429977) | Cod sursa (job #707316) | Cod sursa (job #35837) | Cod sursa (job #1358628) | Cod sursa (job #1808225)
#include <iostream>
#include <fstream>
#include <string.h>
#define pmax 2000099
using namespace std;
char p[pmax],s[pmax];
int sol[pmax],nr,urm[pmax];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{int k,m,n,i;
fin.getline(p,pmax);
m=strlen(p);
urm[0]=-1;k=-1;
for(i=1;i<m;i++)
{ while(k>=0 && p[k+1]!=p[i])k=urm[k];
if(p[k+1]==p[i])k++;
urm[i]=k;
}
k=-1;
fin.getline(s,pmax);
n=strlen(s);
for(i=0;i<n;i++)
{ while(k>=0 && p[k+1]!=s[i])k=urm[k];
if(p[k+1]==s[i])k++;
if(k==m-1)
{if(nr<1000)sol[++nr]=i-m+1;
else nr++;
k=urm[k];
}
}
fout<<nr<<'\n';
for(i=1;i<=min(nr,1000);i++)fout<<sol[i]<<'\n';
}