Cod sursa(job #3310258)

Utilizator razviii237Uzum Razvan razviii237 Data 12 septembrie 2025 14:15:33
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
//#include <iostream>
#include <fstream>
#include <set>
#include <queue>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int maxn = 2e6+5;
string a, b;
int prefix[maxn];
vector<int> answers;

signed main()
{
    cin >> a >> b;

    // prefix calculation
    int index = -1;
    prefix[0] = -1;
    for(int i = 1; i < a.size(); i ++) {
        while(index > 0 && a[i] != a[index + 1]) {
            index = prefix[index];
        }
        if(a[i] == a[index + 1])
            index ++;
        prefix[i] = index;
    }

    // kmp
    int idx_a = 0, idx_b = 0;
    while(idx_b + a.size() - idx_a <= b.size()) {
        while(idx_a < a.size() && a[idx_a] == b[idx_b]) {
            idx_a ++;
            idx_b ++;
        }
        if(idx_a == a.size())
            answers.push_back(idx_b - a.size());
        if(idx_a > 0) // daca ar fi 0, ar ramane tot 0, deci nu trebuie schimbar, + evitam sigsecv
            idx_a = prefix[idx_a - 1] + 1;
        if(idx_a == 0)
            idx_b ++;
    }

    cout << answers.size() << '\n';
    for(auto ans : answers)
        cout << ans << ' ';

    return 0;
}