Cod sursa(job #2325850)

Utilizator igsifvevc avb igsi Data 22 ianuarie 2019 23:16:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<int> processPattern(const std::string& P)
{
    std::vector<int> p(P.size(), -1);
    
    int k;
    for (int i = 1; i < P.size(); ++i)
    {
        k = p[i - 1];
        while (k > -1 && P[k + 1] != P[i])
            k = p[k];
        if (P[k + 1] == P[i])
            ++k;
        p[i] = k;
    }
    
    return p;
}

int main()
{
    std::ifstream fin("strmatch.in");
    std::ofstream fout("strmatch.out");
    
    std::string pattern, text;
    fin >> pattern >> text;
    
    std::vector<int> p = processPattern(pattern);
    
    int matches = 0, pos[1000];
    int k = -1;
    for (int i = 0; i < text.size(); ++i)
    {
        while (k > -1 && pattern[k + 1] != text[i])
            k = p[k];
        if (pattern[k + 1] == text[i])
            ++k;

        if (k == pattern.size() - 1)
        {
            if (matches < 1000) pos[matches] = i - k;
            ++matches;
            k = p[k];
        }
    }
    
    fout << matches << '\n';
    for (int i = 0; i < std::min(1000, matches); ++i)
        fout << pos[i] << ' ';
    fout << std::endl;
    
    return 0;
}