Pagini recente » Cod sursa (job #879592) | Cod sursa (job #3174641) | Cod sursa (job #2252306) | Cod sursa (job #1585611) | Cod sursa (job #1678224)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nextt[2000001],n,m,nr,sol[1001];
char P[2000001],T[2000001];
void urm(char *P)
{
int k=-1;
nextt[0]=0;
for(int i=1; i<m; i++)
{
while(k>0 && P[k+1]!=P[i])
k=nextt[k];
if(P[k+1]==P[i])
k++;
nextt[i]=k;
}
}
int main()
{
int x=-1;
fin>>P>>T;
n=strlen(T);
m=strlen(P);
urm(P);
for(int i=0; i<n; i++)
{
while(x>0 && P[x+1]!=T[i])
x=nextt[x];
if(P[x+1]==T[i])
x++;
if(x==m-1)
{
nr++;
if(nr<1001)
sol[nr]=i-m+1;
x=nextt[x];
}
}
fout<<nr<<'\n';
for(int i=1; i<=min(nr,1000); i++)
fout<<sol[i]<<' ';
fout<<'\n';
return 0;
}