Cod sursa(job #3335251)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 22 ianuarie 2026 05:11:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

int main()
{
    string a, b;
    f >> a >> b;

    int n = (int)a.size();

    string s = "#" + a + "#" + b;
    int t = (int)s.size();

    vector<int> z((t + 1), 0);

    int L = 1, R = 1;

    z[1] = n;
    for (int i = 2; i < t; ++i)
    {
        if (i <= R)
            z[i] = min(z[i - L + 1], (R - i + 1));

        while ((i + z[i] < t) && s[(z[i] + 1)] == s[i + z[i]])
            ++z[i];

        if ((i + z[i] - 1) > R)
            L = i, R = (i + z[i] - 1);
    }

    vector<int> v = {};
    for (int i = (n + 2); i < t; ++i)
        if (z[i] == n)
            v.push_back(i - (n + 2));

    g << (int)v.size() << '\n';
    for (int i = 0; i < min(1000, (int)v.size()); ++i)
        g << v[i] << ' ';
    g << '\n';

    return 0;
}