Cod sursa(job #3292855)

Utilizator tedicTheodor Ciobanu tedic Data 9 aprilie 2025 14:53:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>

using namespace std;
int kmp[4000005];
string a,b, s="#";
vector<int>sol;
void KMP()
{
    for(int i=2; i<s.size(); i++)
    {
        int k=kmp[i-1];
        while(k!=0 && s[k+1]!=s[i])
            k=kmp[k];
        if(s[k+1]==s[i])
            kmp[i]=k+1;
        if(kmp[i]==a.size())
            sol.push_back(i-2*a.size()-1);
    }
}
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin>>a>>b;
    s+=a+'#'+b;
    KMP();
    cout<<sol.size()<<'\n';
    for(int i=0; i<min(1000, (int)sol.size()); i++)
        cout<<sol[i]<<" ";
    return 0;
}