Cod sursa(job #3370300)

Utilizator llaris_a23Larisa Alexandra Videnie llaris_a23 Data 25 octombrie 2026 12:04:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>

using namespace std;

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

string A, B;

vector<int> lps;
vector<int> rez;

int main() {

    fin >> A;
    fin >> B;

    int i = 1, len = 0;

    int l1 = A.size() - 1;
    int l2 = B.size() - 1;

    lps.emplace_back(0);

    int cnt = 0;

    while (i <= l1) {
        if (A[i] == A[len]) {
            i++;
            len++;
            lps.push_back(len);
        }
        else {
            if (len != 0) {
                len = lps[len - 1];
            }
            else {
                lps.push_back(len);
                i++;
            }
        }
    }

    i = 0;
    int j = 0;

    while (i <= l2) {
        if (A[j] == B[i]) {
            i++;
            j++;
        }

        if (j == l1 + 1) {
            cnt++;
            rez.emplace_back(i - j);
            j = lps[j - 1];
        }

        if (A[j] != B[i]) {
            if (j != 0) {
                j = lps[j - 1];
            }
            else {
                i++;

            }
        }
    }

    fout << cnt << '\n';

    if (cnt > 1000) {
        for (int k = 0; k < 1000; k++) {
            fout << rez[k] << ' ';
        }
    }
    else {
        for (int k = 0; k < rez.size(); k++) {
            fout << rez[k] << ' ';
        }
    }

}