Cod sursa(job #3300524)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 16 iunie 2025 21:59:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int NMAX=2*1e6+5;
int f[NMAX];
string p, t;

void pref(string p, int m)
{
    int i, k;
    f[0]=-1;
    for(i=1; i<=m; i++)
    {
        k=f[i-1];
        while(k>=0 && p[k]!=p[i-1]) k=f[k];
        f[i]=k+1;
    }
}

void kmp(string t, int n, string p, int m)
{
    int cnt=0, i=0, k=0;
    vector <int> ans;
    while(i<=(n-m+1))
    {
        if(t[i+k]==p[k]) k++;
        else if(k==0) i++;
        else
        {
            i+=k-f[k];
            k=f[k];
        }
        if(k==m)
        {
            cnt++;
            if(cnt<=1000) ans.push_back(i);
        }
    }
    cout<<cnt<<'\n';
    for(auto i:ans) cout<<i<<' ';
}

int main()
{
    cin>>p;
    cin>>t;
    pref(p, p.size());
    kmp(t, t.size(), p, p.size());
    return 0;
}