Cod sursa(job #3160327)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 23 octombrie 2023 18:15:37
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 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 (int i = 0; i < min(999, (int)res.size()); i++)
        fout << res[i] << ' ';

    return 0;
}