Cod sursa(job #3349342)

Utilizator AswVwsACamburu Luca AswVwsA Data 28 martie 2026 14:12:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <cassert>
#include <vector>
#define ll long long
using namespace std;

const int NMAX = 2e6;

int pozitie[NMAX + 1];
int vecin[NMAX + 1];

vector <int> sol;

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    int i;
    string a, b;
    cin >> a >> b;
    a = "!" + a;
    b = "!" + b;

    vecin[1] = 0;
    vecin[0] = -1;
    for (i = 2; i < a.size(); i++)
    {
        int ax = vecin[i - 1];
        while (ax > -1 and a[ax + 1] != a[i])
            ax = vecin[ax];
        vecin[i] = ax + 1;
    }
    /*for (i = 1; i < a.size(); i++)
        cout << vecin[i] << " ";
    cout << "\n";*/

    pozitie[0] = 0;
    for (i = 1; i < b.size(); i++)
    {
        int ax = pozitie[i - 1];
        if (ax == a.size())
            ax = vecin[ax];
        while (ax > -1 and a[ax + 1] != b[i])
            ax = vecin[ax];
        pozitie[i] = ax + 1;
    }
    /*for (i = 1; i < b.size(); i++)
        cout << pozitie[i] << " ";
    cout << "\n";*/

    for (i = 1; i < b.size(); i++)
        if (pozitie[i] == a.size() - 1)
            sol.push_back(i - 1 - pozitie[i] + 1);

    cout << sol.size() << "\n";
    sol.resize(min((int)sol.size(), 1000));
    for (int x : sol)
        cout << x << " ";
}