Cod sursa(job #3156602)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 11 octombrie 2023 21:08:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <string>

using namespace std;

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

const int N = 1e6;
int z[N + 1];

string pat, s;

int main()
{
    cin >> pat >> s;
    s = pat + '@' + s;
    int n = s.size();
    int m = pat.size();
    for (int i = 1, l = 0, r = 0; i < n; ++i)
    {
        if (i <= r)
        z[i] = min (z[i - l], r - i + 1);
        while (i + z[i] < n && s[i + z[i]] == s[z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            r = i + z[i] - 1, l = i;
    }
    int nr = 0;
    for (int i = m + 1; i < n; ++i)
        if (z[i] == m)++nr;
    cout << nr << '\n';
    nr = 0;
    for (int i = m + 1; i < n; ++i)
        if (z[i] == m && nr + 1 <= 1000)
            ++nr, cout << i - m - 1 << ' ';
    return 0;

}