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

Автор Ehsan_sShuvo, история, 8 лет назад, По-английски

why in Z algorithm substring length is bound-1? please,explain this anyone.

Z[k] would be longest substring starting at k which is also prefix of the string. Now R-i + 1 gives the length of remaining characters in the Z box. Since we copy the value of Z[k] to optimize the calculation of Z values we need to check whether these values are inside the boundary of the Z box

Why not we calculate the remaining part including k index?K index is in the substring,so why skip this index?

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

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

If you put the code/pseudo code and point out where you got stuck at, then people would find it easier to help you out

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    yep! int k1=i-left; if(Z_value[k1]<right-k1+1) ///why not Z_Value[k1]<=right-k1+1 Z_value.push_back(Z_value[k1]); else { left=i; while(right<(int)final_string.size() && final_string[right]==final_string[right-left]) right++; Z_value.push_back(right-left); right--; }

    i got a logic for my problem.that is if we don't use bound-1,we will compare the next value of bound(that means bound+1 index) whether it is in the pattern list or not ` am i right,brother?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Start using pastebin. It preserves code indentation and helps the reader.