Cod sursa(job #2322226)

Utilizator EmplopiStefan Nitu Emplopi Data 17 ianuarie 2019 16:35:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

char a[2000002], b[2000002];
int sol[2000000], pi[2000001];

int main(){
    FILE *fin, *fout;
    int i, lc, n=1, m=1, nsol=0;
    fin=fopen("strmatch.in", "r");
    fout=fopen("strmatch.out", "w");
    b[1]=fgetc(fin);
    while(b[n]!='\n')
        b[++n]=fgetc(fin);
    a[1]=fgetc(fin);
    while(a[m]!='\n')
        a[++m]=fgetc(fin);
    n--;
    m--;
    pi[1]=0;
    lc=0;
    for(i=2;i<=n;i++){
        while(lc>0 && b[i]!=b[lc+1])
            lc=pi[lc];
        if(b[i]==b[lc+1])
            lc++;
        pi[i]=lc;
    }
    //for(i=1;i<=n;i++)
        //printf("%d ", pi[i]);
    //printf("\n");
    lc=0;
    for(i=1;i<=m;i++){
        while(lc>0 && a[i]!=b[lc+1])
            lc=pi[lc];
        if(a[i]==b[lc+1])
            lc++;
        //printf("lc: %d\n", lc);
        if(lc==n)
            sol[nsol++]=i;
    }
    fprintf(fout, "%d\n", nsol);
    for(i=0;i<nsol && i<1000;i++)
        fprintf(fout, "%d ", sol[i]-n);
    fclose(fin);
    fclose(fout);

    return 0;
}