Cod sursa(job #3352043)

Utilizator Andreea1501013Andreea Andreea1501013 Data 23 aprilie 2026 11:50:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
///KMP
#include <bits/stdc++.h>

using namespace std;

int LPS[2000005];
int cnt=0,poz[1005];
string f,s;
void generateLPS()
{
    int pref=0;
    for(size_t suf=1; suf<f.size(); suf++)
    {
        while(pref!=0 && f[pref]!=f[suf])
        {
            pref=LPS[pref-1];
        }
        if(f[pref]==f[suf])
        {
            pref++;
        }
        LPS[suf]=pref;
    }
}

void findStr()
{
    size_t j=0;
    for(size_t i=0; i<s.size(); i++)
    {
        while(j!=0 && f[j]!=s[i])
        {
            j=LPS[j-1];
        }
        if(s[i]==f[j])
        {
            j++;
            if(j==f.size())
            {
                cnt++;
                if(cnt<=1000)
                {
                    poz[cnt]=i-j+1;
                }
                j=LPS[j-1];
            }
        }
    }
}
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin>>f>>s;
    generateLPS();
    findStr();
    cout<<cnt<<'\n';
    for(int i=1; i<=min(cnt,1000); i++)
    {
        cout<<poz[i]<<' ';
    }
    return 0;
}