Cod sursa(job #3310263)

Utilizator razviii237Uzum Razvan razviii237 Data 12 septembrie 2025 14:35:21
Problema Potrivirea sirurilor Scor 100
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() - 1 - idx_a < b.size()) {
        while(idx_a < a.size() && idx_b < b.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)
            idx_a = prefix[idx_a - 1] + 1;
        else
        {
            idx_b ++;
        }
    }

    cout << answers.size() << '\n';
    for(int i = 0; i < min(1000, (int)answers.size()); i ++)
        cout << answers[i] << ' ';

    return 0;
}