Cod sursa(job #3321098)

Utilizator AlexRadu010Radu Alexandru Timotei AlexRadu010 Data 8 noiembrie 2025 10:46:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
#include<string>
#include<vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s,t;
vector <int> a;
int v[2000005],m,n,nr;
void rez(){
    int l=0,i=1;
    while(i<m){
        if(s[l]==s[i])
            ++l,v[i]=l,++i;
        else if(l)
            l=v[l-1];
        else
            v[i]=0,++i;
    }
}
void kmp(){
    int l=0,i=0;
    while(i<n){
        if(t[i]==s[l]){
            ++l,++i;
            if(l==m){
                a.push_back(i-m);
                l=v[l-1];
            }
        }
        else if(l)
            l=v[l-1];
        else
            ++i;
    }
}
signed main(){
    cin>>s>>t;
    m=s.size();
    n=t.size();
    rez();
    kmp();
    cout<<a.size()<<'\n';
    a.resize(min((int)a.size(),1000));
    for(auto i:a)
        cout<<i<<' ';
}