Cod sursa(job #3151288)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 20 septembrie 2023 15:56:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 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);
                if (ans.size() == 1000)
                    break;
                j = p[j];
            }
        }
    }

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