Cod sursa(job #3329777)

Utilizator coco11coraline kalbfleisch coco11 Data 15 decembrie 2025 18:11:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> prefix_function(const string &s){
    int n = s.size();
    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;
    }
    return pi;
}

signed 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; cin>>A>>B;
    vector<int> pi = prefix_function(A);

    vector<int> occ;
    int j=0;
    for(int i=0;i<(int)B.size();i++){
        while(j>0 && B[i]!=A[j]) j=pi[j-1];
        if(B[i]==A[j]) j++;
        if(j==(int)A.size()){
            occ.push_back(i-(int)A.size()+1);
            j=pi[j-1];
        }
    }

    cout<<occ.size()<<"\n";
    for(int i=0;i<min((int)occ.size(),1000LL);i++){
        cout<<occ[i]<<" ";
    }
    cout<<"\n";
    return 0;
}