Cod sursa(job #3212257)

Utilizator AlexInfoIordachioaiei Alex AlexInfo Data 11 martie 2024 14:41:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

const int NMAX = 2e6 + 30;
const int INF = 0x3f3f3f3f;

char s[NMAX], t[NMAX];
int pi[NMAX], n, m;
vector<int> ans;

void read()
{
    in >> s;
    in >> t;
    n = strlen(s), m = strlen(t);
    for (int i = n; i >= 1; i--)
        s[i] = s[i - 1];
    for (int i = m; i >= 1; i--)
        t[i] = t[i - 1];

    cout << n;
}

void sufix()
{
    // pi[i] -> cea mai lunga subsecventa din M care incepe in M[i]
    ///(cel mai lung prefix a lui M care este sufix a lui M[i]);
    pi[1] = 0;
    for (int i = 2, k = 0; i <= n; i++)
    {
        while (k > 0 && s[k + 1] != s[i])
            k = pi[k];
        if (s[k + 1] == s[i])
            k++;
        pi[i] = k;
    }
}

void solve()
{
    sufix();
    for (int i = 1, k = 0; i <= m; i++)
    {
        while (k > 0 && s[k + 1] != t[i])
            k = pi[k];
        if (s[k + 1] == t[i])
            k++;
        if (k == n)
            k = pi[n], ans.pb(i - n + 1);
    }

    out << ans.size() << '\n';
    int i = 0;
    for (auto it : ans)
    {
        i++;
        if (i <= 1000)
            out << it - 1 << ' ';
        else
            break;
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    read();
    solve();

    return 0;
}