Pagini recente » Cod sursa (job #1346500) | Cod sursa (job #711949) | Cod sursa (job #789742) | Cod sursa (job #2885895) | Cod sursa (job #218548)
Cod sursa(job #218548)
#include <stdio.h>
#include <string.h>
#define N 2000100
char t[N],p[N];
int poz[N],m,i,n,rez[1010],kont;
void prefix()
{
int i,k=0;
for (i=2; i<=m; i++)
{
while (k && p[k+1]!=p[i]) k=poz[k];
if (p[k+1]==p[i]) k++;
poz[i]=k;
}
}
void kmp()
{
int i,k=0;
for (i=1; i<=n; i++)
{
while (k && p[k+1]!=t[i]) k=poz[k];
if (p[k+1]==t[i]) k++;
if (k==m)
{
if (kont<1000) rez[++kont]=i-m;
else kont++;
k=poz[k];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(p+1,N,stdin);
fgets(t+1,N,stdin);
m=strlen(p+1)-1;
n=strlen(t+1)-1;
kont=0;
prefix();
kmp();
printf("%d\n",kont);
if (kont>1000) kont=1000;
for (i=1; i<=kont; i++) printf("%d ",rez[i]);
return 0;
}