Cod sursa(job #3347748)

Utilizator cKalbfleischcoraline Kalbfleisch cKalbfleisch Data 18 martie 2026 10:08:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    string a,b,s;cin>>a>>b;
    s=a+'#'+b;
    int kmp[s.length()];
    kmp[0]=0;
    for(int i=1;i<s.length();i++){
        kmp[i]=kmp[i-1];
        while(kmp[i]>0 && s[i]!=s[kmp[i]]){
            kmp[i]=kmp[kmp[i]-1];
        }
        if(s[i]==s[kmp[i]]){
            kmp[i]=kmp[i]+1;
        }
    }
    int v=a.length();
    int cnt=0;
    queue<int> q;
    for(int i=0;i<s.length();i++){
        if(kmp[i]==v){
            cnt++;
            q.push(i-(2*a.length()));
        }
    }
    cout<<cnt<<'\n';
    while(!q.empty()){
        cout<<q.front()<<' ';
        q.pop();
    }
}