Cod sursa(job #2846450)

Utilizator tibinyteCozma Tiberiu-Stefan tibinyte Data 9 februarie 2022 11:26:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    string a, b;
    fin >> a >> b;
    int n = a.size();
    int m = b.size();
    string s = '$' + a + '$' + b;
    int x = (int)s.size() - 1;
    vector<int> pi(x + 1);
    for (int i = 2; i <= x; ++i) {
        int j = pi[i - 1];
        while (j && s[j + 1] != s[i]) {
            j = pi[j];
        }
        if (j == 0) {
            pi[i] = (s[1] == s[i]);
        }
        else {
            pi[i] = j + 1;
        }
    }
    int cnt = 0;
    for (int i = n+2; i <= n + m+1; ++i) {
        if (pi[i] == n) {
            cnt++;
        }
    }
    int nr = 0;
    fout <<  cnt << '\n';
    for (int i = n + 2; i <= n + m + 1; ++i) {
        if (pi[i] == n) {
            nr++;
            fout << i - 2 * n - 1 << ' ';
        }
        if (nr == 1000) {
            break;
        }
    }
}