Cod sursa(job #1172534)

Utilizator fromzerotoheroFROM ZERO fromzerotohero Data 17 aprilie 2014 17:11:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

#define nmax 2000005

int i, j, n, m;
int pi[nmax], sol[nmax];
// Pi[i] = lungimea celui mai lung prefix din P care este si sufix in P
char P[nmax], T[nmax];

void pp(){
    
    pi[1] = 0;
    
    int q = 0;
    
    for (i=2; i<=m; ++i){
        while (q>0 && P[q+1] != P[i]) q = pi[q];
        if (P[q+1] == P[i]) ++q;
        pi[i] = q;
    }
    
}

void kmp(){
    
    pp();
    
    for (int i=1, q=0; i<=n; i++){
        while (q>0 && P[q+1] != T[i]) q = pi[q];
        if (P[q+1] == T[i]) ++q;
        if (q == m){
            sol[++sol[0]] = i - m;
            q = pi[q];
        }
    }
    
}

int main(){
    
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    
    in >> (P+1);
    in >> (T+1);
    
    m = strlen(P+1);
    n = strlen(T+1);
    
    kmp();
    
    out << sol[0] << "\n";
    
    if (sol[0] > 1000) sol[0] = 1000;
    
    for (i=1; i<=sol[0]; i++)
        out << sol[i] << " ";
    
    out << "\n";
    
    return 0;
}