6
\$\begingroup\$

Let us define prefix-function(string)[i] as the length of the largest prefix of string, which is also a suffix of string[1..i], and z-function(string)[i] is the length of the largest prefix of string, which is also a prefix of string[i..].

Unfortunately, there is very little information on them in English, but I found a presentation on Knuth-Morris-Pratt algorithm containing description of prefix-function and an article on z-function.

Here is my implementation of prefix-function and z-function and conversions between them in linear time on the length of string using pure C++. Comments are appreciated! In particular, I'm interesting how to determine a string from z-function directly.

std::vector<int> prefix_function (const std::string& str) {
    std::vector<int> prefs (str.size(), 0);
    for (int i = 1; i < str.size(); ++i) {
        int pref = prefs[i-1];
        while (pref > 0 && str[i] != str[pref]) {
            pref = prefs[pref-1];
        }
        if (str[i] == str[pref]) {
            ++pref;
        }
        prefs[i] = pref;
    }
    return prefs;
}

std::vector<int> z_function(const std::string& str) {
    std::vector<int> zfunc (str.size(), 0);
    zfunc[0] = str.size();
    for (int i = 1, left = 0, right = 0; i < str.size(); ++i) {
        if (i <= right) {
            zfunc[i] = std::min (right - i + 1, zfunc[i - left]);
        }
        while (i + zfunc[i] < str.size() && str[zfunc[i]] == str[i + zfunc[i]]) {
            ++zfunc[i];
        }
        if (i + zfunc[i] - 1 > right) {
            left = i;
            right = i + zfunc[i] - 1;
        }
    }
    return zfunc;
}

std::string from_prefix_function(const std::vector<int>& prefs) {
    std::string str (prefs.size(), '.');
    char current_symbol = 'a';
    for (int i = 0; i < prefs.size(); ++i) {
        if (prefs[i] > 0) {
            str[i] = str[prefs[i] - 1];
        } else {
            str[i] = current_symbol++;
        }
    }
    return str;
}

std::vector<int> prefix_to_z(const std::vector<int>& prefs) {
    return z_function(from_prefix_function(prefs));
}

std::vector<int> z_to_prefix(const std::vector<int>& z_func) {
    std::vector<int> prefs (z_func.size(), 0);
    for (int i = 1; i < z_func.size(); ++i) {
        prefs[i + z_func[i] - 1] = std::max(prefs[i + z_func[i] - 1], z_func[i]);
    }
    for (int i = z_func.size() - 2; i >= 0; --i) {
        prefs[i] = std::max(prefs[i+1] - 1, prefs[i]);
    }
    return prefs;
}
\$\endgroup\$
2
\$\begingroup\$

This will be a somewhat strange answer but the thing is that I can't find anything wrong with your code: it is not that easy to understand what it is doing, but it is only because the algorithms are not the most straightforward in the world; if we compare your code and the algorithms pseudo-code, it's easy to see that they are performing the same computations. Everything seems well-written, the language is used as it should be used... In the end, I only have a few almost-irrelevant remarks left:

  • The only obvious thing you could do is to templatize your algorithm so that it works for any std::basic_string specialization and not only for std::string.

  • If you strive for speed and can overcome a little less readability (generally, you don't), you could try to change this piece of code:

    if (str[i] == str[pref]) {
        ++pref;
    }
    

    into this one:

    pref += str[i] == str[pref];
    

    But even then, time it, time it again, and I'm pretty sure that the compiler is somehow smart enough to get rid of that branch for you and that it won't impact the overall speed of the algorithm in any significant way.

  • You are slightly inconsistent in the way you call the functions: you wrote std::min (/* ... */) but also std::max(/* ... */). You should either put a space everywhere or remove it everywhere, but be consistent.

Well, as you see, there is little to say about what you wrote. It's some pretty good code. Great job writing it! :)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.