Savior-of-Cross's blog

By Savior-of-Cross, 4 years ago, In English

I was solving the string section problems from Brazilian summer camp 2018, and there were following problems:

You are given z-function of some (unknown for you) string s, write prefix-function of the string s.

You are given prefix-function of some (unknown for you) string s, write z-function of the string s.

I thought that if these were solvable, just storing all the equality information would suffice on both problems, and they indeed got AC (Code below). But I have no clue how to prove either of these, and I couldn't find the editorial on google.

Can someone tell me how to prove these?

z->pi
pi->z
  • Vote: I like it
  • +40
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +44 Vote: I do not like it

You can try to google translate this adamant's blog

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I found this simple conversion too

Edited: Sorry :( It should have an extra loop too

vector<int> pi(n + 1, 0);
for (int i = 0; i < n; ++i) maximize(pi[i + z[i] - 1], z[i]);
for (int i = n; i > 0; --i) maximize(pi[i - 1], pi[i] - 1);
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wow.. that was really nice

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Unfortunately, it does not work. Consider string $$$s = "aaaa"$$$. $$$P(s)=[1,2,3]$$$, $$$Z(s)= [3,2,1]$$$ (3 values because we can skip the very first letter). Following $$$P\rightarrow Z$$$ conversion, during 3 iterations we will set $$$Z_1$$$ to $$$1$$$, $$$2$$$, and $$$3$$$, but won't touch other elements at all.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        :(

        The correct version seems to have an extra for-loop

        z->pi

        I wonder if there's something simple for pi->z as well. I couldn't get the same correction work for it.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          You can find a simple version here (the comment is in Russian, but all you need is code).

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            thanks. I got the general ideas on why those two codes work but I feel like I'm still missing the "key" reason why they form a one-to-one correspondence in the first place.

            Like, the characteristic of the equivalence classes of strings with the same prefix function (or equivalently, the same z-function as shown by these two codes). Maybe I should just study some string processing course instead...

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              Rev. 2   Vote: I like it +8 Vote: I do not like it

              String classes are rather simple: take all prefixes of the string, for the prefix of each length, find a set of all its occurrences in the string. If for two strings these sets are equal for all lengths, you cannot distinguish them, and vice versa.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          hey, I was trying to understand the algorithm from adamant's blog and I came with this one. It does the same and uses more memory, but I found it better to understand.

          • by p-func, s[0:p[i]] == s[i-p[i]+1:i]
          • the substr starting at (i-p[i]+1) is a prefix of s
          1. mark all positions where pref-func indicates a start of a pref-substr. now, the missing values in z are substr of the already marked substrs

          2. try to fill the inside positions using values of the prefix once a new marked substring starts, start this greedy filling again from this new marked string

          these may have a intersection, you can compute the same stuff for both marked strings, but the new one will lead to higher values and we need to maximize stuff here, so just look at the new one.

          int main(){
            int n; cin >> n;
            vector<int> z(n);
          
            vector<int> marked;
            for(int i = 0; i < n; ++i){
              int x; cin >> x; if(i == 0) continue;
              if(x){
                z[i - x + 1] = x;
                marked.push_back(i - x + 1);
              }
            }
            for(int i = 0; i < marked.size(); ++i){
              int r = (i + 1 == marked.size()? n : marked[i + 1]);
              int pos = marked[i];
              for(int j = 1; j < z[pos] && pos + j < r; ++j){
                int val = min(z[j], z[pos] - j);
                z[pos + j] = val;
              }
            }
          
            for(auto x : z) cout << x << " "; cout << endl;
          }
          
»
4 years ago, # |
  Vote: I like it +393 Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

.