Cod sursa(job #929379)

Utilizator sebii_cSebastian Claici sebii_c Data 26 martie 2013 23:44:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

typedef vector<int>::iterator iter;

vector<int> prefix(const string& str)
{
    vector<int> pi(str.size(), 0);

    int k = 0;
    for (int i = 1; i < str.size(); ++i) {
        while (k > 0 && str[i] != str[k])
            k = pi[k - 1];

        if (str[i] == str[k])
            ++k;
        pi[i] = k;
    }

    return pi;
}

vector<int> match(const string& str, const string& patt)
{
    vector<int> matches;
    vector<int> pi = prefix(patt);

    int k = 0;
    for (int i = 0; i < str.size(); ++i) {
        while (k > 0 && str[i] != patt[k])
            k = pi[k - 1];

        if (str[i] == patt[k])
            ++k;
        if (k == patt.size())
            matches.push_back(i - patt.size() + 1);
    }

    return matches;
}

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

    string str, patt;
    fin >> patt >> str;

    vector<int> matches = match(str, patt);

    fout << static_cast<int>(matches.size()) << endl;
    for (iter it = matches.begin(); it != matches.end(); ++it)
        fout << *it << " ";
    fout << endl;

    return 0;
}