furious's blog

How to compute z-function having prefix func. already computed?
By furious, 11 years ago, In Russian

I'd be grateful if anyone could explain it to me. Thanks in advance!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Actually, you can construct a string with current prefix-function, then calculate its z-function. The way to construct string is following: just iterate through the symbols of alphabet, try to add symbol to current string and check if value of prefix-function is correct — if it really is, just add this symbol to current string, if not — continue iterating. If you can't add any symbol, there's no string with such prefix-function values.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    One can construct the example much easier: s[i] = s[prefix[i]-1], and than check the answer.

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

    Isn't this correct?

    Your code here...
for(int i=0;i<n;i++)
  if(prefix[i]!=0)
    z[i-prefix[i]+1]=max(z[i-prefix[i]+1],prefix[i]);

    where z and prefix arrays are z-function and prefix functions respectively

    → Reply