Cod sursa(job #1073015)

Utilizator harababurelPuscas Sergiu harababurel Data 5 ianuarie 2014 15:51:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define nmax 2000005
using namespace std;

string p, t;
vector <int> sol;
int b[nmax];

void preprocess() {
    int i=0, j=-1;

    b[0] = -1;
    while(i < int(p.size())) {
        while(j >= 0 && p[i] != p[j]) j = b[j];
        b[++i] = ++j;
    }
}

void kmp() {
    int i=0, j=0;
    while(i < int(t.size())) {
        while(j >= 0 && t[i] != p[j]) j = b[j];
        i++; j++;
        if(j == int(p.size())) {
            sol.push_back(i-j);
            j = b[j];
        }
    }
}



int main() {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    getline(f, p);
    getline(f, t);

    preprocess();
    kmp();

    g<<sol.size()<<"\n";
    for(int i=0; i<min(1000, int(sol.size())); i++) g<<sol[i]<<" "; g<<"\n";


    return 0;
}