Cod sursa(job #3293701)

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