Cod sursa(job #1821372)

Utilizator mihai.alphamihai craciun mihai.alpha Data 2 decembrie 2016 23:18:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
FILE *fin, *fout;
 ///Algoritmul z praduitorilor
#define MAXN 2000000

int n, m;
char N[1+2*MAXN];

int Z[1+2*MAXN];

int st[1+MAXN], last=0;

int main(){
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    char c=fgetc(fin);
    while(c!='\n'){
        N[++n]=c;
        c=fgetc(fin);
    }
    m=n;
    c=fgetc(fin);
    while(c!='\n'){
        N[++n]=c;
        c=fgetc(fin);
    }

    int L=1, R=1;
    for(int k=2;k<=n;k++){
        if(k>R){
            int i=1, j=k;
            while(j<=n && N[i]==N[j]){i++;j++;}
            i--;j--;
            L=k;R=j;
            Z[k]=R-L+1;
        }
        else{
            int k2=k-L+1;
            if(Z[k2]<R-k+1)
                Z[k]=Z[k2];
            else{
                int i=R-k+2, j=R+1;
                while(j<=n && N[i]==N[j]){i++;j++;}
                i--;j--;

                L=k;R=j;
                Z[k]=j-k+1;
            }
        }
        if(k>m && Z[k]>=m)
            st[++last]=k-m-1;
    }
    fprintf(fout, "%d\n", last);
    if(last>1000)
        last=1000;
    for(int i=1;i<=last;i++)
        fprintf(fout, "%d ", st[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}