Pagini recente » Cod sursa (job #1914416) | Cod sursa (job #2513330) | Cod sursa (job #1646787) | Cod sursa (job #3238853) | Cod sursa (job #1689410)
#include <iostream>
#include <fstream>
#include <string.h>
#define nmax 2000999
using namespace std;
char s[nmax],p[nmax];
long n,urm[nmax],sol[nmax],nr;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void pref()
{long i,k;
urm[0]=-1; k=-1;
for(i=1;i<n;i++)
{
while(k>=0 && p[k+1]!=p[i])k=urm[k];
if(p[k+1]==p[i])k++;
urm[i]=k;
}
}
int main()
{long m,x,i;
fin.getline(p,nmax);
fin.getline(s,nmax);
n=strlen(p);
pref();
x=-1;
m=strlen(s);
for(i=0;i<m;i++)
{
while(x>=0 && p[x+1]!=s[i])x=urm[x];
if(p[x+1]==s[i])x++;
if(x==n-1)
{
if(nr<1000)
sol[++nr]=i-n+1;
else nr++;
x=urm[x];
}
}
fout<<nr<<endl;
for(i=1;i<=min(nr,(long)1000);i++)
fout<<sol[i]<<' ';
}