Cod sursa(job #301203)

Utilizator hasegandaniHasegan Daniel hasegandani Data 7 aprilie 2009 23:50:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<string.h>

#define Nmax 2000002

char T[Nmax],P[Nmax];
int m,n,v[1010],pi[Nmax];

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

void KMP()
{
    int i,k=0;
    for(i=1;i<=m;++i)
        {
            while (k>0 && T[k+1]!=P[i])
                k=pi[k];
            if (T[k+1]==P[i])
                k=k+1;
            if (k==n)
                {
                ++v[0];
                if (v[0]<=1000)
                    v[v[0]]=i-n;
                k=pi[k];
                }
        }
}

int main()
{
    int i;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",T);
    scanf("%s",P);
    
    n=strlen(T); m=strlen(P);
    
    for(i=n;i;--i) T[i]=T[i-1]; T[0]=' ';
    for(i=m;i;--i) P[i]=P[i-1]; P[0]=' ';
    
    prefix();
    KMP();
    
    printf("%d\n",v[0]);
    if (v[0]>1000) v[0]=1000;
    for(i=1;i<=v[0];++i)
        printf("%d ",v[i]);
    printf("\n");
        
    return 0;
}