Cod sursa(job #3244794)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 26 septembrie 2024 16:40:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

int n, m;
string a, b;

int main() {
    in >> a;
    n = a.length();

    in >> b;
    m = b.length();

    vector<int> p(n, -1);

    p[0] = -1;
    int j = -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]) {
            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];
            if (ans.size() == 1000) {
                break;
            }
        }
    }

    out << ans.size() << '\n';

    for (auto it : ans) {
        out << it << " ";
    }
    return 0;
}