Cod sursa(job #330706)

Utilizator IoannaPandele Ioana Ioanna Data 11 iulie 2009 12:09:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#include<string.h>
#define nmax 2000010
char a[nmax],b[nmax];
long k[nmax],n,m,nr,poz[1010];

void read()
{
scanf("%s",a);
scanf("%s",b);
n=strlen(b);
m=strlen(a);
}

void border()
{
long i,j;
i=0;
j=-1;
k[0]=-1;
while (i<m)
      {
       while (j>=0 && a[j]!=a[i])
              j=k[j];
       i++;
       j++;
       if (a[i]==a[j])
           k[i]=k[j];
       else k[i]=j;
      }
}

void kmp()
{
long i,j;
i=j=0;
while (i<n)
      {
       while (j>=0 && b[i]!=a[j])
              j=k[j];
       i++;j++;
       if (j>=m)
          {
           nr++;
           if (nr<=1000)
           poz[++poz[0]]=i-j;
           j=k[j];
          }
      }
}

int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
border();
kmp();
printf("%ld\n",nr);
long i;
for (i=1;i<=poz[0];i++)
     printf("%ld ",poz[i]);
return 0;
}