Cod sursa(job #3298319)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 28 mai 2025 19:40:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
#define min(a, b) (a < b ? a : b)
#define LEN_MAX (int)2e6 + 5
#define SOL_MAX 1000

using namespace std;

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

string A, B;

int pi[LEN_MAX];

vector<int> sol;

int main() {
    fin >> A >> B;

    pi[0] = 0;
    for (int i = 1; i < A.size(); i++) {
        if (A[i] == A[pi[i - 1]]) {
            pi[i] = pi[i - 1] + 1;
        }
        else {
            int idx = pi[i - 1];
            while (idx != 0 && A[i] != A[idx]) {
                idx = pi[idx - 1];
            }
            if (A[i] == A[idx]) {
                idx++;
            }
            pi[i] = idx;
        }
    }

    int idx = 0;
    for (int i = 0; i < B.size(); i++) {
        if (idx < A.size() && B[i] == A[idx]) {
            idx++;
            if (idx == A.size()) {
                sol.push_back(i + 1 - A.size());
                idx = pi[idx - 1];
            }
        }
        else {
            while (idx != 0 && B[i] != A[idx]) {
                idx = pi[idx - 1];
            }
            if (B[i] == A[idx]) {
                idx++;
            }
        }
    }

    fout << sol.size() << "\n";
    for (int i = 0; i < min(SOL_MAX, sol.size()); i++) {
        fout << sol[i] << " ";
    }
    return 0;
}