Cod sursa(job #3273179)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 1 februarie 2025 11:16:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
// #include <iostream>
#include <string>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int main()
{
    string A, B;
    cin >> A >> B;

    string match = A + "#" + B;

    vector<int> p((int)match.size() + 1, 0);

    for (int i = 1; i < p.size(); i++)
    {
        int j = p[i - 1];
        while (j > 0 and match[i] != match[j])
        {
            j = p[j - 1];
        }
        if (match[i] == match[j])
            j++;
        p[i] = j;
    }
    int ans = 0;
    // for (int i = 0; i < match.size(); i++)
    // {
    //     cout << match[i] << " ";
    // }

    vector<int> ans_pos;
    for (int i = 0; i < p.size(); i++)
    {
        if (p[i] == A.size())
        {
            if (ans < 1000)
            {
                ans_pos.push_back(i - A.size());
            }
            ans++;
        }
    }

    cout << ans << '\n';

    for (int i = 0; i < ans_pos.size(); i++)
    {
        cout << ans_pos[i] - A.size() << " ";
    }

    return 0;
}