Cod sursa(job #3274192)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 5 februarie 2025 17:48:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;

inline vector<int> prefix_function(string s) {
    int n = s.size();
    vector<int> pi(n);
    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;
    }
    return pi;
}

inline vector<int> kmp(string a, string b) {
    int n = b.size(), m = a.size();
    vector<int> pi = prefix_function(a);
    vector<int> rez;
    int i = 0, j = 0;
    while(i < n) {
        if(b[i] == a[j]) {
            i++, j++;
            if(j == m) rez.push_back(i - j), j = pi[j - 1];
        }
        else {
            if(j > 0) j = pi[j - 1];
            else i++;
        }
    }
    return rez;
}

int main()
{
    fin >> a >> b;
    vector<int> rez = kmp(a, b);
    fout << rez.size() << '\n';
    for(int i : rez) fout << i << " ";

    return 0;
}