Cod sursa(job #3272972)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 31 ianuarie 2025 20:28:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>

using namespace std;

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

string a, b;

void make_prefix(string &a, vector<int> &p)
{
    int n = a.size();
    p.resize(n);
    for (int i = 1; i < n; ++i)
    {
        int j = p[i - 1];
        while (j && a[i] != a[j])
            j = p[j - 1];
        if (a[i] == a[j])
            ++j;
        p[i] = j;
    }
}

int count_occurences(string &a, int len, vector<int> &p)
{
    int cnt = 0;
    for (int i = len + 1; i < a.size(); ++i)
        cnt += p[i] == len;
    return cnt;
}

int main()
{
    fin >> a >> b;
    int len = a.size();
    b = a + '#' + b;
    vector<int> p;
    make_prefix(b, p);
    fout << count_occurences(b, len, p) << '\n';
    int cnt = 1000, i = len + 1;
    while (cnt && i < b.size())
    {
        if (p[i] == len)
        {
            fout << i - 2 * len << ' ';
            --cnt;
        }
        ++i;
    }

    return 0;
}