Cod sursa(job #3321070)

Utilizator cristian46290Petre Cristian cristian46290 Data 8 noiembrie 2025 10:13:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>

std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");

using namespace std;
typedef long long int ll;

const int nMax = 2e6 + 5;

int lps[nMax], rez[nMax], nrr;
string s, t;

void prefixsufix(string s)
{
    int m = s.size(), lg = 0;
    int i = 1;
    while(i < m){
        if (s[i] == s[lg])lg++,lps[i] = lg,i++;
        else if (lg != 0)lg = lps[lg-1];
        else lps[i++] = 0;
    }
}

void KMP(string t,string s)
{
    int n = t.size(), m = s.size();
    int lg = 0, i = 0;
    while(i < n){
        if (t[i] == s[lg]){
            lg++,i++;
            if (lg == m)rez[++nrr] = i - m,lg = lps[lg-1];
        }
        else if (lg != 0)lg = lps[lg-1];
        else i++;
    }
}

void solve()
{
    prefixsufix(s);
    KMP(t,s);
    g << nrr << '\n';
    for (int it = 1;it <= min(1000,nrr);it++)g << rez[it] << " ";
}

int main()
{
    getline(f,s);
    getline(f,t);
    solve();
}