Cod sursa(job #3309147)

Utilizator calinarulMarinescu Calin calinarul Data 1 septembrie 2025 21:27:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2 * 1e6 + 5;
vector<int> lps(NMAX, 0);
void pre_built(string pattern)
{
    lps[0] = 0;
    int lenght = 0;
    int i = 1;
    int m = pattern.size();
    while (i < m)
    {
        if (pattern[i] == pattern[lenght])
        {
            lenght++;
            lps[i] = lenght;
            i++;
        }
        else
        {
            if (lenght > 0)
            {
                lenght = lps[lenght - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}
void kmp(string a, string b)
{
    vector<int> pozitii;
    int i = 0;
    int j = 0;
    int n = a.size();
    int m = b.size();
    while (i < n)
    {
        if (a[i] == b[j])
        {
            i++;
            j++;
        }
        else
        {
            if (j != 0)
            j = lps[j - 1];
            else
            i++;
        }
        if (j == m)
        {
            pozitii.push_back(i - j);
            if (pozitii.size() == 1000)
            {
                fout << pozitii.size() << '\n';
                for (int q : pozitii)
                    fout << q << ' ';
                return;
            }
            j = lps[j - 1];
        }
    }
    fout << pozitii.size() << '\n';
    for (int q : pozitii)
        fout << q << ' ';
}
int main()
{
    string a, b;
    fin >> b;
    fin.ignore();
    fin >> a;
    pre_built(b);
    kmp(a, b);
}