Cod sursa(job #335300)

Utilizator ZillaMathe Bogdan Zilla Data 29 iulie 2009 14:43:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <string.h>

#define Nmax 2001000

char a[Nmax],b[Nmax];
int pi[Nmax],cont,l,l2,v[1100];


void gen()
{
    int i,k=0;
    pi[1]=0;
    for(i=2;i<=l;++i)
        {
            while(a[k+1]!=a[i] && k>0)
                k=pi[k];
            if(a[k+1]==a[i])
                ++k;
            pi[i]=k;
        }
}

void comp()
{
    int i,k=0;
    for(i=1;i<=l2;++i)
        {
            while(a[k+1]!=b[i] && k>0)
                k=pi[k];
            if(a[k+1]==b[i])
                ++k;
            if(k==l)
                {
                    ++cont;
                    if(cont<1000)
                        v[cont]=i-l;
                    k=pi[l];
                }
        }
}

int main()
{
    int i;
    
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    gets(a+1);
    gets(b+1);
    
    l=strlen(a+1);
    l2=strlen(b+1);
    
    gen();
    comp();
    
    printf("%d\n",cont);
    if(cont>1000)
        for(i=1;i<=1000;++i)
            printf("%d ",v[i]);
    else
        for(i=1;i<=cont;++i)
            printf("%d ",v[i]);
  //  printf("%s %d\n%s %d",a+1,l,b+1,l2);
    return 0; 
}