Mai intai trebuie sa te autentifici.

Cod sursa(job #3292231)

Utilizator mihaigeorgescuGeorgescu Mihai mihaigeorgescu Data 7 aprilie 2025 17:27:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fcin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
inline vector <int> precalc(const string &s)
{
    vector <int> rez(s.size());
    int i=1, j=0; rez[0]=0;
    while(i<s.size())
    {
        if(s[i]==s[j])
        {
            j++;
            rez[i]=j;
            i++;
        }
        else
        {
            if(j!=0)
            {
                j=rez[j-1];
            }
            else
            {
                rez[i]=0;
                i++;
            }
        }
    }
    return rez;
}
inline void kmp(const string &a, const string &b)
{
    vector <int> lps, rez;
    lps=precalc(a);
    int i=0, j=0;
    while(i<b.size())
    {
        if(b[i]==a[j])
        {
            i++;
            j++;
        }
        else
        {
            if(j!=0)
            {
                j=lps[j-1];
            }
            else
            {
                i++;
            }
        }
        if(j==a.size())
        {
            rez.push_back(i-a.size());
        }
    }
    fout<<rez.size()<<'\n';
    for(auto i : rez)
        fout<<i<<" ";
}
int main()
{
    fcin>>a>>b;
    kmp(a,b);
    return 0;
}