Cod sursa(job #2883124)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 1 aprilie 2022 10:37:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e6 + 6;
int pi[3 * NMAX];

void buildPi(string &a)
{
    int i, j;
    pi[0] = 0;

    for(i = 1; i < a.length(); ++i)
    {
        j = pi[i-1];

        while(j != 0 && a[j] != a[i])
            j = pi[j-1];

        if(a[j] == a[i])
            ++j;

        pi[i] = j;
    }

}

int main()
{
    string a, b;
    vector <int> sol;
    fin >> a >> b;

    int i, siz = a.length();
    i = a.length() + 1;

    a = a + "#" + b;
    buildPi(a);

    for(; i < a.length(); ++i)
        if(pi[i] == siz)
            sol.push_back(i - (siz + 1) - siz + 1);

    fout << sol.size() << '\n';
    int j = 0;
    for(auto &it: sol)
    {
        ++j;
        fout << it << ' ';

        if(j == 1000)
            break ;
    }
    return 0;
}