Cod sursa(job #3170457)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 17 noiembrie 2023 18:02:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
#define MAXSZ 2000001

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n, m, p[MAXSZ] = {0};
char a[MAXSZ], b[MAXSZ];

int main() {
    fin >> b >> a;
    n = (int) strlen(a);
    m = (int) strlen(b);

    p[0] = 0;
    p[1] = 0;
    int q = 0;
    for (int i = 2; i <= m; i++) {
        while (q > 0 && b[q] != b[i - 1])
            q = p[q];
        if (b[q] == b[i - 1])
            q++;
        p[i] = q;
    }

    int j = 0;
    vector<int> matches;
    for (int i = 0; i < n; i++) {
        while (j > 0 && a[i] != b[j])
            j = p[j];
        if (a[i] == b[j])
            j++;
        if (j == m) {
            matches.push_back(i - m + 1);
            j = p[j];
        }
    }

    fout << matches.size() << '\n';
    for (auto& i: matches)
        fout << i << ' ';
}