Cod sursa(job #2269429)

Utilizator ZanoxNonea Victor Zanox Data 25 octombrie 2018 22:54:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <string>
#include <cstring>
#include <vector>

int* zFunction(std::string s)
{
    int len = s.size();
    int* zf = new int[len];
    memset(zf, '\0', len * sizeof(int));

    for(int i=1, l=0, r=0; i<len; i++)
    {
        if(i > r)
        {
            int j=i;
            while(j < len && s[j-i] == s[j])j++;
            zf[i] = j - i;
            if(zf[i] > 0)
            {
                l = i;
                r = j-1;
            }
        }
        else
        {
            zf[i] = std::min(zf[i-l], r - i + 1);

            int j = i + zf[i];
            while(j < len && s[j-i] == s[j])j++;
            zf[i] = j - i;

            l = i;
            r = j-1;

        }
    }
    return zf;
}

int main()
{
    std::string a,b;
    std::ifstream fin("strmatch.in");
    std::ofstream fout("strmatch.out");

    fin>>a>>b;

    b = a + b;

    int* zf = zFunction(b);
    std::vector<int> sol;
    for(int i = a.size(); i < b.size(); i++)
        if(zf[i] >= a.size())sol.push_back(i - a.size());
    fout<<sol.size()<<'\n';
    for(int i=0; i<std::min(1000, (int)sol.size()); i++)
        fout<<sol[i]<<' ';
    fout<<'\n';
}