Cod sursa(job #2843315)

Utilizator PopaMihaimihai popa PopaMihai Data 2 februarie 2022 12:23:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 4e6 + 2;

int z[NMAX], ans[NMAX];
string a, b, S;

int mymin(int a, int b)
{
    return (a < b ? a : b);
}

int main()
{
    fin >> a >> b;


    S = "$" + a;
    S.push_back('$');
    S += b;

    int sz = S.size() - 1;
    int L = 0, R = 0;
    z[1] = sz;

    for(int i = 2; i <= sz; i++) {
        if(i <= R)
            z[i] = mymin(z[i - L + 1], R - i + 1);
        else z[i] = 0;

        while(i + z[i] <= sz && S[i + z[i]] == S[z[i] + 1])
            z[i]++;

        if(R < i + z[i] - 1)
            L = i, R = i + z[i] - 1;
    }

    for(int i = 2; i <= sz; i++) {
        if(z[i] >= a.size())
            ans[++ans[0]] = i  - a.size() - 2;
    }

    fout << ans[0] << '\n';
    for(int i = 1; i <= mymin(ans[0], 1000); i++)
        fout << ans[i] << " ";
    fout << '\n';
    return 0;
}