Cod sursa(job #269043)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 2 martie 2009 11:39:25
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#include <string.h>
#define nmax 2000001

char A[nmax],B[nmax],p[nmax];
int n,m,nr,s[1001];

int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);

scanf("%s\n",A+1);
scanf("%s",B+1);

n = strlen(A+1);
m = strlen(B+1);

int k=0,i;

for (i=2;i<n;i++)
{
while (k>0 && A[i]!=A[k+1]) k=p[k];
if (A[i]==A[k+1]) k++;
p[i]=k;
}

k=0;

for (i=1;i<m;i++)
{
while (k>0 && B[i]!=A[k+1]) k=p[k];
if (B[i]==A[k+1]) k++;
if (k==n)
{
nr++;
if (nr<=1000) s[nr] = i-n;
k = p[k];
}
}
printf("%d\n",nr);
if (nr>1000) nr=1000;
for (i=1;i<=nr;i++) printf("%d ",s[i]);

return 0;
}