Cod sursa(job #613311)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 21 septembrie 2011 12:53:05
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <cstring>

#define max_n 2000002

using namespace std;

int n,m,i,j,nr;
char p[max_n],t[max_n];
int l[max_n];
int sol[1001];

ifstream in("kmp.in");
ofstream out("kmp.out");

void prefix() {
    int i,k=0;
    l[1]=0;
    for (i=2; i<=n; i++) {
         k=l[i-1];
         while (k!=0 && p[i]!=p[k+1])
               k=l[k];
         if (p[i]==p[k+1]) k++;
         l[i]=k;
    }
}

void kmp() {
    int i,k=0;
    for (i=1; i<=m; i++) {
        while (k!=0 && t[i]!=p[k+1])
               k=l[k];
        if (t[i]==p[k+1]) k++;
        if (k==n) {
           if (nr<1000) sol[++nr]=i-n+1;
           k=l[n];
        }
    }
}

int main () {
    in.getline(p+1,max_n);
    in.getline(t+1,max_n);
    n=strlen(p+1);
    m=strlen(t+1);

    nr=0;
    prefix();
    kmp();

    out << nr << '\n';
    for (i=1; i<=nr; i++)
        out << sol[i]-1 << ' ';
    out << '\n';
    return 0;
}