KMP 中partial match table generation的一个问题# JobHunting - 待字闺中
i*u
1 楼
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-a
上面链接中的len = lps[len-1]; 怎么证明 为什么不是len = len -1, 因为lps[len-1
]是前面那个子串的lps最大长度，而不是整个当前子串的
例如 ABAD___ABAA ,当A与D 不match的时候 我们直接去看ABAD中的B而不是A ， 怎么
证明不存在可能性：ABA match
BAA, 我知道由于前面的ABAD与ABAA不能match导致了这种结果 可以忽略ABA 直接看ABA
中得最长lps， 即AB,因为ABA的lps是1, 但是我无法证明这个东西一定成立 不知道大
家怎么理解的？
上面链接中的len = lps[len-1]; 怎么证明 为什么不是len = len -1, 因为lps[len-1
]是前面那个子串的lps最大长度，而不是整个当前子串的
例如 ABAD___ABAA ,当A与D 不match的时候 我们直接去看ABAD中的B而不是A ， 怎么
证明不存在可能性：ABA match
BAA, 我知道由于前面的ABAD与ABAA不能match导致了这种结果 可以忽略ABA 直接看ABA
中得最长lps， 即AB,因为ABA的lps是1, 但是我无法证明这个东西一定成立 不知道大
家怎么理解的？