Cod sursa(job #2325848)

Utilizator igsifvevc avb igsi Data 22 ianuarie 2019 23:07:05
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <string>
#include <tuple>
#include <vector>

std::vector<int> get_prefix_fct(const std::string &pattern)
{
    std::vector<int> prefix(pattern.size());
    int k;

    prefix[0] = -1;
    for (size_t i = 1; i < pattern.size(); ++i)
    {
        do
        {
            k = prefix[i - 1];
        } while (k != -1 && pattern[i] != pattern[k + 1]);

        prefix[i] = pattern[i] == pattern[k + 1] ? k + 1 : k;
    }

    return prefix;
}

std::pair<std::vector<int>, int> find(const std::string &pattern, const std::string &text)
{
    std::vector<int> positions(1000),
        prefix = get_prefix_fct(pattern);

    int k = -1, matches = 0;
    for (size_t i = 0; i < text.size(); ++i)
    {
        while (k != -1 && pattern[k + 1] != text[i])
        {
            k = prefix[k];
        }

        k = pattern[k + 1] == text[i] ? k + 1 : -1;

        if (k == pattern.size() - 1)
        {
            k = prefix[k];
            if (matches < 1000)
            {
                positions[matches] = i - pattern.size() + 1;
            }
            matches++;
        }
    }

    return std::make_pair(positions, matches);
}

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

    std::string pattern, text;
    fin >> pattern >> text;

    std::vector<int> positions;
    int matches;

    std::tie(positions, matches) = find(pattern, text);

    fout << matches << '\n';
    for (size_t i = 0; i < positions.size() && i < matches; ++i)
    {
        fout << positions[i] << ' ';
    }
    fout << '\n';

    return 0;
}