Cod sursa(job #3321053)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 8 noiembrie 2025 09:50:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int nmax = 4e6+5;

int rez, lps[nmax];

vector <int> sol;

void kmp (string s, string t)
{
    int n = s.size();
    s = s + "#" + t;
    int k = 0;
    for (int i = 1; i < s.size(); i++)
    {
        while (k != 0 && s[i] != s[k])
            k = lps[k-1];
        if (s[i] == s[k])
            k++;
        lps[i] = k;
        if (lps[i] == n)
        {
            rez++;
            if (rez <= 1000)
                sol.push_back(i - 2 * n);
        }
    }
}

int main()
{
    string s, t;
    fin >> s >> t;
    kmp(s, t);
    fout << rez << '\n';
    for (auto it : sol)
        fout << it << ' ';
    return 0;
}