Cod sursa(job #667347)

Utilizator Tux2NicolaeTelechi Nicolae Tux2Nicolae Data 22 ianuarie 2012 22:04:06
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#include<string.h>
char A[2000010],B[2000010]; int m,n,p[2000010],nr,cout[1001];

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

void mpk(){
    int k=0,i;
    for(i=0;i<=m;i++){
        while(k>0 && A[k]!=B[i]) k=p[k-1];
        if(A[k]==B[i]) k++;
        if(k==n+1) {
            cout[++nr]=i-k+1; k=p[k-1];
        }
    }
}

int main(){
    int i;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",A); scanf("%s",B);
    n=strlen(A)-1; m=strlen(B)-1;
    prefix(); mpk();
    printf("%d\n",nr);
    for(i=1;i<=nr && i<=1000;i++) printf("%d ",cout[i]);
}