Pagini recente » Cod sursa (job #1089661) | Cod sursa (job #125167) | Cod sursa (job #410229)
Cod sursa(job #410229)
#include <cstdio>
#include <cstring>
#define file_in "strmatch.in"
#define file_out "strmatch.out"
#define Nmax 2410000
int i,k,n,m,pi[Nmax];
char a[Nmax];
char b[Nmax];
int nr,sol[Nmax];
void prefix()
{
k=0;
pi[1]=0;
for (i=2;i<=n;++i)
{
while(a[k+1]!=a[i] && k>0) k=pi[k];
if (a[k+1]==a[i]) k++;
pi[i]=k;
}
}
void kmp()
{
k=0;
nr=0;
for (i=1;i<=m;++i)
{
while(a[k+1]!=b[i] && k>0) k=pi[k];
if (a[k+1]==b[i]) k++;
if (k==n)
{
sol[++nr]=i-n;
}
}
}
int main()
{
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%s\n", a+1);
n=strlen(a+1);
scanf("%s\n", b+1);
m=strlen(b+1);
prefix();
kmp();
printf("%d\n", nr);
for (i=1;i<=nr && i<=1000;++i)
printf("%d ", sol[i]);
fclose(stdin);
fclose(stdout);
return 0;
}