Cod sursa(job #320262)

Utilizator TyberFMI Dogan Adrian Ioan Lucian Tyber Data 4 iunie 2009 10:21:50
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<stdio.h>
#define nmax 2000010   
char a[nmax],b[nmax];   
void pref();   
void kmp();   
int min(int,int);   
int n,m,p1[nmax],p2[2000],n1;   
int main(){   
    freopen("strmatch.in","r",stdin);   
    freopen("strmatch.out","w",stdout);   
    fgets(a,sizeof(a),stdin);   
    fgets(b,sizeof(b),stdin);   
    while((a[m]>='A'&&a[m]<='Z')||(a[m]>='a'&&a[m]<='z')||(a[m]>='0'&&a[m]<='9'))m++;   
    while((b[n]>='A'&&b[n]<='Z')||(b[n]>='a'&&b[n]<='z')||(b[n]>='0'&&b[n]<='9'))n++;   
    for(int i=m;i!=0;i--){   
        a[i]=a[i-1];   
        a[0]=' ';   
    }   
    for(int i=n;i!=0;i--){   
        b[i]=b[i-1];   
        b[0]=' ';   
    }   
    pref();   
    kmp();   
    printf("%d\n",n1);   
    for(int i=1;i<=min(n1,1000);i++)   
        printf("%d ",p2[i]);   
    printf("\n");   
    return 0;   
}   
void pref(){   
    int i,c=0;   
    for(i=2,p1[1]=0;i<=m;i++){   
        while(c&&a[c+1]!=a[i])   
            c=p1[c];   
        if(a[c+1]==a[i])   
            c++;   
        p1[i]=c;   
    }   
}   
void kmp(){   
    int i,c=0;   
    for(i=1;i<=n;i++){   
        while(c&&a[c+1]!=b[i])   
            c=p1[c];   
        if(a[c+1]==b[i])   
            c++;   
        if(c==m){   
            c=p1[m];   
            n1++;   
            if(n1<=1000)   
                p2[n1]=i-m;   
        }   
    }   
}   
int min(int a,int b){   
    if(a<b)return a;   
    else return b;   
}