Cod sursa(job #3185215)

Utilizator not_anduAndu Scheusan not_andu Data 18 decembrie 2023 14:46:36
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"

void solve(){

    string s, aux; cin >> s >> aux;
    int lung = s.length();
    s += '#';
    s += aux;

    int n = s.length();
    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;
    }

    vector<int> ans;
    for(int i = lung; i < n; ++i){
        if(pi[i] == lung){
            ans.push_back(i - (lung + 3));
        }
    }

    cout << ans.size() << '\n';
    for(auto &nr : ans){
        cout << nr << " ";
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}