Cod sursa(job #3292803)

Utilizator tedicTheodor Ciobanu tedic Data 9 aprilie 2025 13:15:20
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
string a,b,suport;
vector<int>sol;
int L[4000005];

void zalgorithm()
{
    int best=0;
    for(int i=1; i<suport.size(); i++)
    {
        int rightBound=best+L[best];
        int j=i-best;
        if(i<=rightBound)
            L[i]=min(L[j], rightBound-i);
        while(i+L[i]+1<suport.size() && suport[L[i]+1]==suport[i+L[i]+1])
            L[i]++;
        if(i+L[i]>rightBound)
            best=i;
        //cout<<i<<" "<<L[i]<<'\n';
        if(L[i]==a.size()-1 && sol.size()<1000)
            sol.push_back(i-a.size()-1);
    }
}
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin>>a>>b;
    L[0]=1;
    suport+=a;
    suport+='#';
    suport+=b;
    /// suport = a#b
    zalgorithm();
    cout<<sol.size()<<'\n';
    for(int i=0; i<sol.size(); i++)
        cout<<sol[i]<<" ";
    return 0;
}