Cod sursa(job #2921433)

Utilizator bigmixerVictor Purice bigmixer Data 31 august 2022 01:10:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define fr first
#define sc second
//#define int long long
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 4000005;

int pref[nmax];
string A, B;

void KMP(){
    int last = 0;
    for(int i=1;i<A.size();i++){
        last = i - 1;
        while(last >= 1 && A[i] != A[pref[last]]){
            last = pref[last] - 1;
        }
        if(A[i] == A[pref[last]]) pref[i] = pref[last] + 1;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    cin >> A >> B;
    int n = A.size();
    int m = B.size();
    A = A + "$" + B;
    KMP();
    vector <int> ans;
    for(int i=0;i<A.size();i++){
        if(pref[i] >= n){
            ans.push_back(i - 2*n );
        }
    }
    cout << ans.size() << '\n';
    for(int i=0;i<min((int)ans.size(), 1000);i++){
        cout << ans[i] << ' ';
    }
}