Cod sursa(job #1171978)

Utilizator fromzerotoheroFROM ZERO fromzerotohero Data 16 aprilie 2014 16:52:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

#define nmax 2000005

long n, m;
int i, j;
int overlap[nmax];

vector <int> sol;
string pattern, text;

void pp(){

    i = 0;
    
    overlap[0] = overlap[1] = 0;
    
    for (j = 2; j <= m; j++){
    
        i = overlap[j-1];
        
        while (1){
        
            if (pattern[j-1] == pattern[i]){
                overlap[j] = i + 1;
                break;
            } else if (i == 0) {
                overlap[j] = 0;
                break;
            }
        
            i = overlap[i];
        
        }
    }
        
}

void kmp(){

    j = 0;
    i = 0;
    
    while (i <= n)
        if (text[i] == pattern[j]){
            i++;
            j++;
            if (j == m) sol.push_back(i-m);
        } else if (j > 0) j = overlap[j];
        else i++;
    
}

int main(){
    
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    
    getline(in, pattern);
    getline(in, text);
    
    n = text.size();
    m = pattern.size();
    
    pp();
    kmp();
    
    int g;
    
    if (sol.size() < 1000)
        g = sol.size();
    else g = 1000;
        
    
    out << g << "\n";
    for (i=0; i<g; i++)
        out << sol[i] << " ";
    out << "\n";
    
    return 0;
}