Cod sursa(job #3160323)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 23 octombrie 2023 18:11:36
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int pi[2000002];
vector<int> res;

int main() {

    string pattern, text;
    fin >> pattern >> text;

    int n = pattern.size(), m = text.size();

    pi[1] = 0;
    int k = 0;
    for (int i = 2; i <= n; i++) {
        while (k > 0 && pattern[k] != pattern[i - 1]) {
            k = pi[k];
        }
        if (pattern[k] == pattern[i - 1])
            k++;
        pi[i] = k;
    }

    k = 0;
    for (int i = 2; i <= m; i++) {
        while (k > 0 && pattern[k] != text[i - 1]) {
            k = pi[k];
        }
        if (pattern[k] == text[i - 1])
            k++;

        if (k == n) {
            res.push_back(i - n);
        }
    }

    fout << res.size() << '\n';
    for (auto val : res)
        fout << val << ' ';

    return 0;
}