Mai intai trebuie sa te autentifici.

Cod sursa(job #2888682)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 11 aprilie 2022 18:57:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;
string a, b;
int z[(int)4e6 + 5], ans[1001];
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin >> a >> b;
    b = a + '|' + b;
    int l, r;
    l = r = 0;
    for(int i = 1 ; i < b.size () ; ++ i)
    {
        if (i <= r)
        {
            z[i] = min (z[i - l], r - i + 1);
        }
        while (i + z[i] < b.size () && b[z[i]] == b[i + z[i]])
        {
            ++z[i];
        }
        if (i + z[i] - 1 > r)
        {
            r = i + z[i] - 1;
            l = i;
        }
    }
    int cnt (0);
    for(int i = a.size () + 1 ; i < b.size (); ++ i)
    {
        if (z[i] == a.size ())
        {
            ++cnt;
            if (cnt <= 1000)
                ans[cnt] = i - a.size () - 1;
        }
    }
    cout << cnt << '\n';
    for(int i = 1 ; i <= min (1000, cnt) ; ++ i)
    {
        cout << ans[i] << ' ';
    }
    return 0;
}