带你轻松理解KMP算法
KMP（The Knuth-Morris-Pratt Algorithm）算法用于字符串匹配，从字符串中找出给定的子字符串。但它并不是很好理解和掌握。而理解它概念中的部分匹配表，是理解 KMP 算法的关键。这里的讨论绕开其背后晦涩难懂的逻辑，着重从其运用上来理解它。字符串查找比如从字符串 abcdef 中找出 abcdg 子字符串。朴素的解法，我们可以这样做，分别取出第一位进行匹配，如果相同再取出各自的第二位。如果不同，则将索引后移一位，从总字符串第二位开始，重复步骤一。这种朴素解法的弊端在于，每次匹配失