Cod sursa(job #2717159)

Utilizator marius004scarlat marius marius004 Data 6 martie 2021 15:06:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

vector < int > kmp(const string& s, const string& pattern) {

    vector < int > pi(pattern.size() + 5, 0);
    vector < int > occurrences;

    for(int i{2}, k{}; i < pattern.size();++i) {

       for(;k && pattern[k + 1] != pattern[i];)
           k = pi[k];

       if(pattern[k + 1] == pattern[i])
           k++;

       pi[i] = k;
    }

    for(int i{1}, k{};i < s.size();++i) {

        for(;k && pattern[k + 1] != s[i];)
            k = pi[k];

        if(pattern[k + 1] == s[i])
            k++;

        if(k == pattern.size() - 1) {
            occurrences.push_back(i - pattern.size() + 1);

            if(occurrences.size() > 1000)
                return occurrences;
        }
    }

    return occurrences;
}

int main() {

    string s, pattern;
    f >> pattern >> s;

    s = " " + s;
    pattern = " " + pattern;

    auto sol = kmp(s, pattern);

    g << sol.size() << '\n';
    for(auto& it : sol)
        g << it << ' ';

    return 0;
}