Cod sursa(job #3366159)

Utilizator cKalbfleischcoraline Kalbfleisch cKalbfleisch Data 29 septembrie 2026 16:46:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;

bool INP=true;


int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    if(INP){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    }
    string A,B;cin>>A>>B;
    string S=A+'#'+B;
    int kmp[S.size()];
    kmp[0]=0;
    for(int i=1;i<S.size();i++){
        kmp[i]=kmp[i-1];
        while(kmp[i]>0 && S[kmp[i]] != S[i]){
            kmp[i]=kmp[kmp[i]-1];
        }
        if(S[kmp[i]]==S[i])kmp[i]++;
    }
    int cnt=0;
    vector<int> res;
    for(int i=0;i<S.size();i++){
        if(kmp[i]==A.size()){
            cnt++;
            if(res.size()<1000){
                res.push_back(i-2*A.size());
            }
        }
    }
    cout<<cnt<<'\n';
    for(auto i: res){
        cout<<i<<' ';
    }
}