Cod sursa(job #3228476)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 8 mai 2024 12:50:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;


const string TASK("strmatch");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout


const int N = 4e6 + 9;

int pi[N];

int main()
{
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();

    a = a + '$' + b;

    for(int i = 1; i <= n + m; ++i)
    {
        int j = pi[i - 1];

        while(j && a[j] != a[i])
            j = pi[j - 1];

        if(a[j] == a[i])j ++;

        pi[i] = j;
    }

    int cnt = 0;
    vector<int> app;
    FOR(i, n, n + m)
        if(pi[i] == n)
        {
            cnt ++;
            if(app.size() < 1000)
                app.push_back(i - 2 * n);
        }

    cout << cnt << '\n';
    for(auto i : app)cout << i << ' ';
    return 0;
}