Cod sursa(job #3298303)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 28 mai 2025 18:46:25
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
#define LEN_MAX (int)2e6 + 5

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];
            }
            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];
            }
        }
    }

    fout << sol.size() << "\n";
    for (int idx: sol) {
        fout << idx << " ";
    }
    return 0;
}