Cod sursa(job #2955408)

Utilizator DKMKDMatei Filibiu DKMKD Data 16 decembrie 2022 22:18:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define L 4000005
#define LIM 1000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a, b, s;
int pi[L];

void KMP() {
    s = a + "#" + b;
    pi[0] = 0;
    int k = 0;
    for (int i = 1; i < (int)s.size(); i++) {
        while (k > 0 && s[k] != s[i])
            k = pi[k - 1];
        if (s[k] == s[i])
            k++;
        pi[i] = k;
    }
}

int main() {
    fin >> a >> b;
    KMP();
    int r = 0;
    for (int i = a.size() + 1; i < (int)s.size(); i++)
        r += (pi[i] == (int)a.size());
    fout << r << "\n";
    int out = 0;
    for (int i = a.size() + 1; i < (int)s.size() && out < LIM; i++)
        if (pi[i] == (int)a.size()) {
            fout << i - 2 * a.size() << " ";
            out++;
        }
    fout << "\n";
    return 0;
}