Cod sursa(job #631441)

Utilizator sunt_emoSunt emo sunt_emo Data 8 noiembrie 2011 01:48:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#define N 2000010

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

int main () {
    in.getline (w,N);
    in.getline (s,N);
    while (w[++m]);
    while (s[++n]);
    pmt[0]=-1;
    for (i=1; i<=m; i++) if (w[i-1]==w[pmt[i-1]]) pmt[i]=pmt[i-1]+1;
    i=0;
    while (k+i<n) {
        if (w[i]==s[k+i]) {
            if (i==m-1) c[l++]=k;
            i++;
        }
        else {
            k=k+i-pmt[i];
            if (pmt[i]>-1) i=pmt[i];
            else i=0;
        }
    }
    out<<l<<"\n";
    if (l>1000) l=1000;
    for (i=0; i<l; i++) out<<c[i]<<" "; out<<"\n";
    return 0;
}