Cod sursa(job #2717252)

Utilizator raducostacheRadu Costache raducostache Data 6 martie 2021 20:38:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

string pattern, text;
vector <int> ans;
int pos;
int lps[2000005];

int main() {
    f >> pattern;
    f >> text;

    for (int i = 1; i < pattern.size(); ++i) {
        if(pattern[pos] == pattern[i])  {
            lps[i] = ++pos;
        }
        else if(pos == 0) {
            lps[pos] = 0;
        }
        else {
            --i;
            pos = lps[pos - 1];
        }
    }
    pos = 0;
    int i = 0;
    while (i < text.size()) {
        if (text[i] == pattern[pos]) {
            ++i;
            ++pos;
        }
        else if(pos == 0)
            ++i;
        else pos = lps[pos - 1];

        if(pos == pattern.size()) {
            // it's a match!!!
            ans.push_back(i - pattern.size());
            if(ans.size() == 1000)
                break;
            pos = lps[pos - 1];

        }
    }
    g << ans.size() << '\n';
    for (auto it:ans)
        g << it << ' ';
    return 0;
}