Cod sursa(job #1790455)

Utilizator preda.andreiPreda Andrei preda.andrei Data 28 octombrie 2016 11:42:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

vector<int> AflaPrefix(const string &s)
{
    vector<int> prefix;
    prefix.push_back(0);

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

vector<int> AflaPotriviri(const string &sir, const string &model)
{
    auto prefix = AflaPrefix(model);
    vector<int> pozitii;

    unsigned lung = 0;
    for (unsigned i = 0; i < sir.size(); ++i) {
        while (lung > 0 && sir[i] != model[lung])
            lung = prefix[lung - 1];
        if (sir[i] == model[lung])
            ++lung;
        if (lung == model.size())
            pozitii.push_back(i - lung + 1);
    }
    return pozitii;
}

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

    string cautat;
    getline(fin, cautat);

    string sir;
    getline(fin, sir);

    auto pozitii = AflaPotriviri(sir, cautat);
    fout << pozitii.size() << "\n";
    for (int poz : pozitii)
        fout << poz << " ";

    return 0;
}