KMP表饱和困难

Question

请解释为什么我们在下面的代码中用nextj-1替换j的值：http://computing.dcu.ie/~humphrys/Notes/String/kmp.html按照链接了解表的概念。

i = 0

next[i] = 0
i++
j = 0


while ( i < m )
{
 if ( pattern[j] == pattern[i] )
 {
     next[i] = j+1
     i++
     j++
 }
 else ( pattern[j] != pattern[i] )
 {
     if ( j > 0 )
      j = next[j-1]   //this part i am not able to figure out
                      //why don't we just decrement j-1?

 else ( j == 0 )
 {
  next[i] = 0
  i++
  j = 0             
 }
 }
 }

Answer 1

在这里，j跟踪匹配的长度，i跟踪当前正在处理的字符串的位置。因此，如果j长度的匹配在i位置失败，则该函数尝试查找小于j长度匹配中最长的匹配值。因此，它将j改为next[j - 1]，将i保持在相同的位置。

注意，nextx包含迄今为止最长匹配的长度。如果长度j在ith索引处的匹配失败，则肯定没有与这里匹配的长度j的文本的前缀。因此，我们应该在j - 1上查找匹配，它一直在尝试，直到找到一个长度为正的匹配，字符串前缀或j值变为0。