Cod sursa(job #3333270)

Utilizator abetAlbert Voiculescu abet Data 12 ianuarie 2026 17:38:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main() {
    ios::sync_with_stdio(false);
    in.tie(nullptr);
    string pattern, txt;
    in >> pattern >> txt;
    int m = pattern.size();
    int n = txt.size();
    vector<int> pi(m, 0);
    for (int i = 1; i < m; i++) {
        int j = pi[i - 1];
        while (j > 0 && pattern[i] != pattern[j])
            j = pi[j - 1];
        if (pattern[i] == pattern[j])
            j++;
        pi[i] = j;
    }
    vector<int> pos;
    long long totalMatches = 0;
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && txt[i] != pattern[j])
            j = pi[j - 1];
        if (txt[i] == pattern[j])
            j++;
        if (j == m) {
            totalMatches++;
            if ((int)pos.size() < 1000)
                pos.push_back(i - m + 1);
            j = pi[j - 1];
        }
    }
    out << totalMatches << "\n";
    for (int x : pos)
        out << x << " ";
    out << "\n";
    return 0;
}