Cod sursa(job #3183722)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 12 decembrie 2023 20:45:12
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector<int> res;
void kmp(const string &s, const string &t) {
    int n = s.size(), m = t.size();

    vector<int> pi(n + 1, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
    }

    vector<int> r(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && t[i] != s[j]) {
            j = pi[j - 1];
        }
        if (t[i] == s[j])
            j++;

        if (j == n) {
            res.push_back(i - n + 1);
        }
    }
}

int main() {

    string s, t;
    fin >> s >> t;

    kmp(s, t);

    fout << res.size() << '\n';
    for (int i = 0; i < min(1000, (int)res.size()); i++) {
        fout << res[i] << ' ';
    }

    return 0;
}