Cod sursa(job #2206846)

Utilizator heisenbugDELETEME heisenbug Data 23 mai 2018 22:23:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <string>
#include <vector>

const size_t MAX_N = 1000;

std::vector<int> get_lps_table(const std::string& str)
{
    std::vector<int> lps(str.size());

    size_t i = 1, len = 0;
    while (i < str.size())
        if (str[i] == str[len])
            lps[i++] = ++len;
        else if (len != 0)
            len = lps[len - 1];
        else
            lps[i++] = 0;

    return lps;
}

int strmatch(const std::string& haystack, const std::string& needle, std::vector<int>& matches, size_t max_matches)
{
    size_t all_matches = 0;

    std::vector<int> lps = get_lps_table(needle);

    size_t i = 0, j = 0;
    while (i < haystack.size()) {
        if (haystack[i] == needle[j]) {
            ++i, ++j;
            if (j == needle.size()) {
                ++all_matches;
                if (matches.size() < max_matches)
                    matches.push_back(i - j);
                j = lps[j - 1];
            }
        } else {
            if (j != 0)
                j = lps[j - 1];
            else
                ++i;
        }
    }

    return all_matches;
}

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

    std::string a, b;
    fin >> a >> b;

    std::vector<int> matches;
    int all_matches = strmatch(b, a, matches, MAX_N);

    fout << all_matches << '\n';
    for (int i : matches)
        fout << i << ' ';

    return 0;
}