Cod sursa(job #3348956)

Utilizator CreditKing69Bogdan Moldovan CreditKing69 Data 24 martie 2026 20:06:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

int n, m;
string a, b;
vector<int>pi;

int main()
{
    in >> a >> b;
    n = a.size();
    m = b.size();
    pi.resize(n + 1, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 and a[i] != a[j]) {
            j = pi[j - 1];
        }
        if (a[i] == a[j]) {
            j++;
        }
        pi[i] = j;
    }
    vector<int>rez;
    int cnt = 0;
    int j = 0;
    for (int i = 0; i < m; i++) {
        while (j > 0 and b[i] != a[j]) {
            j = pi[j - 1];
        }
        if (b[i] == a[j]) {
            j++;
        }
        if (j == n) {
            cnt++;
            if (rez.size() < 1000) {
                rez.push_back(i - n + 1);
            }
            j = pi[j - 1];
        }
    }
    out << cnt << '\n';
    for (int k : rez) {
        out << k << " ";
    }
    return 0;
}