Cod sursa(job #631411)

Utilizator sunt_emoSunt emo sunt_emo Data 7 noiembrie 2011 22:37:15
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <cstring>
#define N 2000010

std::ifstream in ("strmatch.in");
std::ofstream out ("strmatch.out");
char s[N],w[N];
long pmt[N],i,k,c[N],l,n,m,t;

void ff (char *a) {
    t=pmt[0]=-1;
    for (i=1; i<m; i++) if (a[i-1]==a[t]) t=pmt[i]=t+1;
    else t=0;
    pmt[m]=0;
}

void kmp (char *s,char *w) {
    k=0;
    while (k+m<=n) {
        i=0;
        while (s[k]==w[i]&&k<n) {
            k++;
            i++;
            if (i==m) c[l++]=k-i;
        }
        i=pmt[i];
        if (i==-1) {
            k++;
            i=0;
        }
    }
}

int main () {
    in.getline (w,N);
    in.getline (s,N);
    n=strlen (s);
    m=strlen (w);
    ff (w);
    kmp (s,w);
    out<<l<<"\n";
    if (l>1000) l=1000;
    for (i=0; i<l; i++) out<<c[i]<<" ";
    out<<"\n";
    return 0;
}