Cod sursa(job #694938)

Utilizator giuliastefGiulia Stef giuliastef Data 28 februarie 2012 09:27:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
// Potrivirea sirurilor - KMP

#include <cstdio>
#include <cstring>
#define LMAX 2000011
using namespace std;
char a[LMAX],b[LMAX];
int nr,poz[1001],pi[LMAX];
int main()
{
    int i,lg,q;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",a,b);
    lg=strlen(a);
    for(i=1;a[i];i++)
     {
      while( q>0 && a[i]!=a[q])
       q=pi[q-1];
      if(a[i]==a[q])
       q++;
      pi[i]=q;
     }
    
    q=0;
    for(i=0;b[i];i++)
    {
     while(q && a[q]!=b[i])
      q=pi[q-1];
     if(a[q]==b[i])
      q++;
     if(q==lg)
     {
      q=pi[lg-1];
      nr++;
      if(nr<=1000)
       poz[nr]=i-lg+1;
     }
    }
    printf("%d\n",nr);
    for(i=1;i<=nr and i<=1000;i++)
     printf("%d ",poz[i]);
    printf("\n");
    return 0;
}