Cod sursa(job #3157481)

Utilizator poparobertpoparobert poparobert Data 15 octombrie 2023 16:52:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> KMP(string &srch,string &pat)
{
    vector<ll> lps(pat.size());
    ll i,j;
    for(i=1;i<pat.size();i++)
    {
        j=i;
        do
        {
            j=lps[j-1];
        }while(j!=0&&pat[i]!=pat[j]);
        lps[i]=j+(pat[i]==pat[j]);
    }
    vector<ll> rez;
    j=0;
    for(i=0;i<srch.size();i++)
    {
        while(j&&pat[j]!=srch[i])j=lps[j-1];
        if(pat[j]==srch[i])j++;
        if(j==pat.size())rez.emplace_back(i-pat.size()+1),j=lps[j-1];
    }
    return rez;
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    string a,b;
    cin>>a>>b;
    vector<ll> rez=KMP(b,a);
    cout<<rez.size()<<'\n';
    for(ll i=0;i<rez.size()&&i<1000;i++)cout<<rez[i]<<' ';
	return 0;
}