Блог пользователя furious

How to compute z-function having prefix func. already computed?
Автор furious, 12 лет назад, По-русски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить