Cod sursa(job #1341888)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 13 februarie 2015 11:11:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<cstdio>
#include<cstring>
int n,m,l,i,nr,j,v[2001000],p[2001000];
char s[2001000],t[2001000];
FILE *f,*g;
int main(){
    f=fopen("strmatch.in","r");
    g=fopen("strmatch.out","w");
    fscanf(f,"%s%s",s+1,t+1);
    n=strlen(s+1);
    m=strlen(t+1);
    //pentru sirul de cautat calculez,la fiecare pozitie i lungimea unei secvente terimnate acolo, identicacu inceputul sirului si de lungime maxima
    l=0;
    p[1]=0;
    for(i=2;i<=n;i++){
        while(l&&s[l+1]!=s[i])
            l=p[l];
        if(s[i]==s[l+1])
            l++;
        p[i]=l;
    }
    l=0;
    for(i=1;i<=m;i++){
        while(l&&s[l+1]!=t[i])
            l=p[l];
        if(s[l+1]==t[i])
            l++;
        if(l==n)
            v[++nr]=i-n;
    }
    fprintf(g,"%d\n",nr);
    for(i=1;i<=nr;i++){
        if(i>1000)
            return 0;
        fprintf(g,"%d ",v[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}