Cod sursa(job #3197004)

Utilizator tibinyteCozma Tiberiu-Stefan tibinyte Data 25 ianuarie 2024 11:37:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

#define cin fin
#define cout fout

using namespace std;

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

vector<int> z_function(string s)
{
    int n = (int)s.size() - 1;
    vector<int> z(n + 1);
    int l = 0, r = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (i <= r)
        {
            z[i] = min(r - i + 1, z[i - l + 1]);
        }
        while (i + z[i] <= n && s[z[i] + 1] == s[i + z[i]])
        {
            ++z[i];
        }
        if (i + z[i] - 1 > r)
        {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    string a, b;
    cin >> a >> b;
    int n = (int)a.size(), m = (int)b.size();
    vector<int> adam = z_function('$' + a + '$' + b);
    vector<int> rep;
    int ans = 0;
    for (int i = n + 2; i <= n + m + 1; ++i)
    {
        if (adam[i] == n)
        {
            ans++;
            if ((int)rep.size() != 1000)
            {
                rep.push_back(i - (n + 2));
            }
        }
    }
    cout << ans << '\n';
    for (auto i : rep)
    {
        cout << i << ' ';
    }
}

/*
Everything falls apart
Even the people who never frown, eventually break down
The sacrifice of hiding in a lie
Everything has to end
You'll soon find we're out of time left to watch it all unwind
The sacrifice is never knowing
*/