Cod sursa(job #2573067)

Utilizator RagnoRazvan Petec Ragno Data 5 martie 2020 15:41:01
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define input "strmatch.in"
#define output "strmatch.out"

const int lMax = 2000003;

using namespace std;

char a[lMax], b[lMax];
int n, m, k, q, ans1;
int pi[lMax];
int ans2[1001];

main()
{
    freopen(input, "rt", stdin);
    freopen(output, "wt", stdout);

    cin >> a + 1 >> b + 1;
    n = strlen(a + 1);
    m = strlen(b + 1);

    k = 0;
    pi[1] = 0;
    for (int i = 2; i <= n; ++i)
    {
        while (k && a[k + 1] != a[i])
            k = pi[k];

        if (a[k + 1] = a[i])
            ++k;
        pi[i] = k;
    }

    q = 0;

    for (int i = 1; i <= m; ++i)
    {
        while (q && a[q + 1] != b[i])
            q = pi[q];
        if (a[q + 1] == b[i])
            ++q;
        if (q == n)
        {
            ++ans1;
            if (ans1 <= 1005) ans2[ans1] = i - n;
        }
    }

    cout << ans1 << "\n";
    for (int i = 1; i <= min(ans1, 1000); ++i)
        cout << ans2[i] << " ";

    return 0;
}