Cod sursa(job #1813724)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 23 noiembrie 2016 11:18:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <cctype>
#define MAXN 2000000
char A[MAXN*2+1];
int pi[MAXN*2+1];
int poz[1001];
int main(){
    FILE*fi,*fout;
    int i,n,k,ans,l;
    char a;
    fi=fopen("strmatch.in" ,"r");
    fout=fopen("strmatch.out" ,"w");
    a=fgetc(fi);
    n=0;
    while(isalpha(a)){
        A[++n]=a;
        a=fgetc(fi);
    }
    l=n;
    a=fgetc(fi);
    while(isalpha(a)){
        A[++n]=a;
        a=fgetc(fi);
    }
    k=0;
    for(i=2;i<=n;i++){
        while(k>0&&A[i]!=A[k+1])
          k=pi[k];
        if(A[k+1]==A[i])
            k++;
        pi[i]=k;
    }
    ans=0;
    for(i=2*l;i<=n;i++){
        if(ans<1000){
          if(pi[i]>=l){
            ans++;
            poz[ans]=i-2*l;
          }
        }
        else
           if(pi[i]>=l)
            ans++;
    }
    fprintf(fout,"%d\n" ,ans);
    for(i=1;i<=ans&&i<=1000;i++)
       fprintf(fout,"%d " ,poz[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}