Pagini recente » Cod sursa (job #1202805) | Cod sursa (job #2077358) | Cod sursa (job #436110) | Cod sursa (job #2318971) | Cod sursa (job #1946936)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int Urm[2000001],n,m,sol[1001],nr;
char T[2000005],P[2000005];
void initurm(char *P)
{
int k=-1, x;
Urm[0]=0;
for(x=1; x<m; x++)
{
while(k>0 && P[k+1]!=P[x])
k=Urm[k];
if(P[k+1]==P[x])
k++;
Urm[x]=k;
}
}
int main()
{int i, x=-1;
f.getline(P,2000004);
f.getline(T,2000004);
n=strlen(T);
m=strlen(P);
initurm(P);
for(i=0; i<n; i++)
{
while(x>0 && P[x+1]!=T[i])
x=Urm[x];
if(P[x+1]==T[i])
x++;
if(x==m-1)
{nr++;
if(nr<=1000)
sol[nr]=i-m+1;
x=Urm[x];}
}
g<<nr<<'\n';
nr=min(nr,1000);
for(i=1; i<=nr; i++)
g<<sol[i]<<" ";
return 0;
}