Cod sursa(job #2722591)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 13 martie 2021 00:17:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>

using namespace std;

string a, b;

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

void getZarr(string str, vector <int>& z)
{
    int n = str.length();

    int l, r, k;

    l = r = 0;

    for (int i = 1; i < n; ++i)
    {
        if (i > r)
        {
            l = r = i;

            while (r < n && str[r - l] == str[r])
                ++r;
            z[i] = r - l;

            --r;
        }

        else
        {
            k = i - l;

            if (z[k] < r - i + 1)
                z[i] = z[k];

            else
            {
                l = i;
                while (r < n && str[r - l] == str[r])
                    ++r;

                z[i] = r - l;

                --r;
            }
        }

    }

}

void search()
{
    string concat = a + "$" + b;
    int l = concat.length();

    vector <int> z(l);

    getZarr(concat, z);

    int cnt = 0;

    for (int i = 0; i < l; ++i)
        if (z[i] == a.length())
            ++cnt;

    fout << cnt << '\n';

    for (int i = 0; i < l; ++i)
        if (z[i] == a.length())
            fout << i - a.length() - 1 << " ";
}


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

    search();

    return 0;
}