furious's blog

By furious, 12 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

»
12 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.

  • »
    »
    12 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.

  • »
    »
    6 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