Cod sursa(job #709993)

Utilizator cmiNCosmin Poieana cmiN Data 8 martie 2012 19:13:26
Problema Potrivirea sirurilor Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;


string str, pat;
vector<int> matchPos, kmpNext;


void init()
{
    kmpNext.resize(str.size());
    int i = 0, j = -1;
    kmpNext[0] = -1;
    while (i < str.size()) {
        while (j > -1 && str[i] != str[j]) j = kmpNext[j];
        ++i, ++j;
        if (str[i] == str[j]) kmpNext[i] = kmpNext[j];
        else kmpNext[i] = j;
    }
}


void solve()
{
    //if (pat.size() > str.size()) return;
    int i = 0, j = 0;
    while (j < pat.size()) {
        while (i > -1 && str[i] != pat[j]) i = kmpNext[i];
        ++i, ++j;
        if (i >= str.size()) {
            if (matchPos.size() == 1000) return; // maxim 1000 pozitii
            matchPos.push_back(j - i);
            i = kmpNext[i];
        }
    }
}


int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> pat >> str;
    init();
    solve();
    fout << matchPos.size() << '\n';
    for (int i = 0; i < matchPos.size(); ++i) fout << matchPos[i] << " ";
    fout << endl;
    fin.close();
    fout.close();
    return 0;
}