Cod sursa(job #2969370)

Utilizator sandry24Grosu Alexandru sandry24 Data 22 ianuarie 2023 21:47:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

vi ans;

vi build_lps(string s){
    int n = s.size();
    vi lps(n);
    for(int i = 1; i < n; i++){
        int j = lps[i-1];
        while(j > 0 && s[i] != s[j])
            j = lps[j-1];
        if(s[i] == s[j])
            j++;
        lps[i] = j;
    }
    return lps;
}

void solve(){
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    vi lps = build_lps(a);
    int i = 0, j = 0;
    while(i < m){
        if(a[j] == b[i]){
            j++;
            i++;
        }
        if(j == n){
            ans.pb(i - n);
            j = lps[j-1];
        } else if(i < m && a[j] != b[i]){
            if(j == 0)
                i++;
            else
                j = lps[j-1];
        }
    }
    cout << ans.size() << '\n';
    for(int i = 0; i < min(1000, (int)ans.size()); i++)
        cout << ans[i] << ' ';
}
 
int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}