Pagini recente » Cod sursa (job #2319445) | Cod sursa (job #1107306) | Cod sursa (job #2386185) | Cod sursa (job #1106621) | Cod sursa (job #1386637)
#include <cstdio>
#include <cstring>
#define LGMAX 2000100
#define min(a,b) a<b?a:b
char N[LGMAX], M[LGMAX];
int pi[LGMAX], pos[1024], n, m,nr;
void citire()
{
gets(N);
gets(M);
}
void make_prefix()
{
n=strlen(N);
int k=0,i;
pi[0]=0;
for(i=1;i<n;++i)
{
while(k&&N[k+1]!=N[i])
k=pi[k];
if(N[k+1]==N[i])
++k;
pi[i]=k;
}
}
void KMP()
{
nr=0;
make_prefix();
m=strlen(M);
n=strlen(N);
int q=0,i;
for(i=0;i<m;++i)
{
while(q&&N[q+1]!=M[i])
q=pi[q];
if(N[q+1]==M[i])
++q;
if(q==n-1)
{
q = pi[n-1];
++nr;
if (nr <= 1000)
pos[nr] = i;
}
}
}
void afisare()
{
int i;
printf("%d\n", nr);
for(i=1;i<=(min(nr,1000));++i)
printf("%d ", pos[i]);
}
void rezolva_problema()
{
citire();
KMP();
afisare();
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
rezolva_problema();
return 0;
}