Cod sursa(job #3278351)

Utilizator Mihai_999Diaconeasa Mihai Mihai_999 Data 19 februarie 2025 15:15:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'

using namespace std;

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

const int NMAX = 4e6+5;

int pi[NMAX], cnt;
string A, B;
vector<int> pozitii;

int main()
{
    fin >> A >> B;
    B = A+"#"+B;
    pi[0] = 0;
    int n = B.size(), j = 0, m = A.size();
    for (int i = 1; i < n; i++)
    {
        while (j > 0 && B[j] != B[i])
            j = pi[j-1];
        if (B[j] == B[i])
            j++;
        pi[i] = j;
        if (pi[i] == m)
        {
            cnt++;
            if (cnt <= 1000)
                pozitii.push_back(i-2*m);
        }
    }
    fout << cnt << nl;
    for (int i : pozitii)
        fout << i << ' ';
    return 0;
}