Cod sursa(job #1485712)

Utilizator DeltaMTP Dragos DeltaM Data 12 septembrie 2015 19:25:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>
#include<cstring>
int n,m,i,j,l,nr,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);
    l=0;
    p[1]=0;
    for(i=2;i<=n;i++){
        while(l!=0&&s[i]!=s[l+1]){
            l=p[l];
        }
        if(s[i]==s[l+1])
            l++;
        p[i]=l;
    }
    l=0;
    for(i=1;i<=m;i++){
        while(l!=0&&s[l+1]!=t[i]){
            l=p[l];
        }
        if(t[i]==s[l+1])
            l++;
        if(l==n)
            v[++nr]=i-n;
    }
    fprintf(g,"%d\n",nr);
    for(i=1;i<=nr;i++){
        if(i>1000)
            break;
        fprintf(g,"%d ",v[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}