Cod sursa(job #3185216)

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

using namespace std;

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

typedef long long ll;

const int VMAX = 2000005;

void solve(){

    string s;

    string a, b;

    cin >> a >> b;

    s.append(a);
    s += '#';
    s.append(b);

    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;

    }

    int cnt = 0;
    vector<int> ans;

    for(int i = 0; i < n; ++i){
        if(pi[i] == a.length()){
            ++cnt;
            ans.push_back(i - a.length() - a.length());
        }
    }

    cout << cnt << '\n';

    for(int i = 0; i < ans.size() && i < 1000; ++i){
        cout << ans[i] << " ";
    }
    cout << '\n';

}

int main(){

    ios_base::sync_with_stdio(false);

    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);

    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}