Cod sursa(job #2748650)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 2 mai 2021 01:11:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

/// Z Algorithm

const int LMAX = 2000000;

string a;
string b;

string sir;

int zBox[1 + 2 * LMAX];

int nrSol;
vector<int> sol;

void zAlgorithm()
{
    int st = 0;
    int dr = 0;

    for (int i = 1; i < sir.size(); i++)
    {
        if (i <= dr)
        {
            zBox[i] = min(zBox[i - st], dr - i + 1);
        }

        while (i + zBox[i] < sir.size() && sir[i + zBox[i]] == sir[zBox[i]])
        {
            zBox[i]++;
        }

        if (i + zBox[i] - 1 > dr)
        {
            st = i;
            dr = i + zBox[i] - 1;
        }
    }
}

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    in >> a >> b;

    sir = a + '$' + b;

    zAlgorithm();

    for (int i = a.size() + 1; i + a.size() - 1 < sir.size(); i++)
    {
        if (zBox[i] == a.size())
        {
            nrSol++;

            if (nrSol <= 1000)
            {
                sol.push_back(i - a.size() - 1);
            }
        }
    }

    out << nrSol << '\n';

    for (int i = 0; i < sol.size(); i++)
    {
        out << sol[i] << ' ';
    }

    return 0;
}