Cod sursa(job #288246)

Utilizator ZillaMathe Bogdan Zilla Data 25 martie 2009 17:39:59
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <string.h>

#define Nmax 2000000
#define Mmax 1001

int n,m,pi[Nmax],nr,vect[Mmax];
char a[Nmax],b[Nmax];

int minim(int a,int b)
{
    if(a<b)
        return a;
    return b;    
}

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

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

        int i,q=0;

        scanf("%s",a);
        scanf("%s",b);
        n=strlen(a);
        m=strlen(b);
        
        for(i=n;i;--i)
            a[i]=a[i-1];
        a[0]=' ';
        for(i=m;i;--i)
            b[i]=b[i-1];
        b[0]=' ';
        
        generare();
         
       for(i=1;i<=m;++i)
            {
                while(q>0 && a[q+1]!=b[i])
                    q=pi[q];
                if(a[q+1]==b[i])
                    ++q;
                if(q==n)
                    {
                        q=pi[n];
                        ++nr;
                        if(nr<=1000)
                            vect[nr]=i-n;
                    }
            }
            
        printf("%d\n",nr);
        q=minim(nr,1000);
        for(i=1;i<=q;++i)
            printf("%d ",vect[i]);
        return 0;
}