Cod sursa(job #3151290)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 20 septembrie 2023 15:59:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
int p[2000005];
int main()
{
    in >> a;
    in >> b;

    int n = a.length();
    int m = b.length();

    int j = -1;
    p[0] = -1;

    for (int i = 1; i < n; i++) {
        while (j >= 0 && a[i] != a[j + 1]) j = p[j];

        if (a[i] == a[j + 1])
            p[i] = j++;
        p[i] = j;
    }

    j = -1;
    vector<int> ans;

    for (int i = 0; i < m; i++) {
        while (j >= 0 && b[i] != a[j + 1]) j = p[j];

        if (b[i] == a[j + 1]) {
            j++;
            if (j == n - 1) {
                ans.push_back(i - n + 1);
                j = p[j];
            }
        }
    }

    out << ans.size() << '\n';
    int sz = ans.size();

    for (int i = 0; i < min(sz, 1000); i++) {
        out << ans[i] << " ";
    }
    return 0;
}