Cod sursa(job #1843419)

Utilizator preda.andreiPreda Andrei preda.andrei Data 8 ianuarie 2017 18:23:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

vector<int> FindPrefixes(const string &s)
{
    vector<int> pref;
    pref.push_back(0);

    int k = 0;
    for (int i = 1; i < s.size(); ++i) {
        while (k > 0 && s[i] != s[k])
            k = pref[k - 1];
        if (s[i] == s[k])
            ++k;
        pref.push_back(k);
    }
    return pref;
}

vector<int> KMP(const string &w, const string &t)
{
    auto prefixes = FindPrefixes(w);
    vector<int> matches;

    int k = 0;
    for (int i = 0; i < t.size() && matches.size() < 1000; ++i) {       
        while (k > 0 && t[i] != w[k])
            k = prefixes[k - 1];
        if (t[i] == w[k])
            ++k;
        if (k == w.size()) {
            matches.push_back(i - w.size() + 1);
            k = prefixes[k - 1];
        }
    }
    return matches;
}

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");

    string word;
    getline(fin, word);

    string text;
    getline(fin, text);

    auto matches = KMP(word, text);
    fout << matches.size() << "\n";
    for (int pos : matches)
        fout << pos << " ";

    return 0;
}