Pagini recente » Istoria paginii runda/pregatire3/clasament | Cod sursa (job #2006864) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1946952)
#include <iostream>
#define minim(a, b) ((a < b) ? a : b)
#include <fstream>
#include <cstring>
int Urm[2000001],n,m,sol[1001],nr;
char T[2000005],P[2000005];
void initurm()
{
int i,k=0;
for(i= 2, Urm[1]=0; i<=m; i++)
{
while(k && P[k+1]!=P[i])
k=Urm[k];
if(P[k+1]==P[i])
k++;
Urm[i]=k;
}
}
int main()
{int i, x=-1;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(P, sizeof(P), stdin);
fgets(T, sizeof(T), stdin);
n=strlen(T);
m=strlen(P);
for(i=m; i>=1; i--)
P[i]=P[i-1];
P[0]=' ';
for(i=n; i>=1; i--)
T[i]=T[i-1];
T[0]=' ';
initurm();
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];}
}
for(i=1; i<=n; i++)
{ while(x && P[x+1]!=T[i])
x=Urm[x];
if(P[x+1]==T[i])
x++;
if(x==m)
{
x=Urm[m];
nr++;
if (nr<= 1000)
sol[nr]=i-m;
}
}
printf("%d\n", nr);
nr=minim(nr,1000);
for(i=1; i<=nr; i++)
printf("%d ", sol[i]);
return 0;
}