KMP算法匹配错误咨询：重复模式串场景下的LPS表疑问

问题场景 #

• 目标字符串：a b c b b c b d a b c b d
• 模式串：a b c b d
• 当前使用的LPS表：0 0 0 2 0

错误匹配过程 #

当匹配到j=4（模式串第5位d）、i=4（目标字符串第5位b）时出现不匹配，后续执行步骤：

• j=2 i=5：匹配字符b
• j=3 i=6：匹配字符c
• j=4 i=7：匹配字符b
• j=5 i=8：匹配字符d

此时算法判定匹配成功，但实际目标字符串中对应的子串是bbcbd，与模式串abcbd不相等，属于误判。

正确的LPS表 #

正确的LPS表应为：0 0 0 1 0

修正原因 #

模式串a b c b d的前缀后缀最长公共长度（LPS）计算逻辑：

• 索引0（字符a）：无有效前后缀，LPS值为0
• 索引1（子串ab）：前缀a与后缀b无公共部分，LPS值为0
• 索引2（子串abc）：所有前缀与后缀均无公共部分，LPS值为0
• 索引3（子串abcb）：最长公共前后缀是单个字符b（前缀a/ab/abc中，仅b与后缀的b匹配），LPS值为1
• 索引4（子串abcbd）：无公共前后缀，LPS值为0

修正LPS表后，当j=4 i=4出现不匹配时，j会跳转到LPS[3]=1的位置，后续匹配逻辑会正常推进，不会出现误判情况。

内容的提问来源于stack exchange，提问作者Irina