Cod sursa(job #3274195)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 5 februarie 2025 18:01:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 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;
}

signed main()
{
    fin >> a >> b;
    vector<int> rez = kmp(a, b);
    fout << rez.size() << '\n';
    int n = rez.size();
    n = min(n, 1000);
    for(int i=0; i<n; i++) fout << rez[i] << " ";

    return 0;
}