Cod sursa(job #2988259)

Utilizator LXGALXGA a LXGA Data 3 martie 2023 21:21:04
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <queue>
#define ll long long
#define mod 998244353
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a, b;
vector<int> ans;
int pi[2000001], n;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b;
    int n = a.size();
    a = a + '#' + b;
    for (int i = 1; i < a.size(); i++)
    {
        int j = pi[i-1];
        while (j > 0 && a[i] != a[j])
            j = pi[j - 1];
        if (a[i] == a[j])
            j++;
        pi[i] = j;
        if (j == n)
            ans.push_back(i - 2 * n);
    }
    cout << ans.size() << '\n';
    for (int i = 0; i < min((int)ans.size() - 1, 999); i++)
        cout << ans[i] << ' ';
    return 0;
}