Cod sursa(job #1172553)

Utilizator fromzerotoheroFROM ZERO fromzerotohero Data 17 aprilie 2014 17:51:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;

char pattern[nmax];
char text[nmax];

int n, m, i, q;

int pi[nmax], sol[nmax];

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

void KMP(){

    preprocess();
    
    for (i=1, q=0; i<=n; i++){
        while  (q>0 && pattern[q+1] != text[i]) q = pi[q];
        
        if (pattern[q+1] == text[i])
            q++;
        if (q == m){
            sol[++sol[0]] = i - m;
            q = pi[q];
        }
        
    }
    
}

int main(){
    
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    
    in >> (pattern + 1);
    in >> (text + 1);
    
    n = strlen(text + 1);
    m = strlen(pattern + 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;
}