对KMP算法的一些理解

KMP算法是一种字符串匹配算法，可以在O(n+m)时间复杂度内实现两个字符串的匹配。

关于字符串匹配

暴力解决字符串匹配即通过两个串的每个字符逐一比较，python实现如下：

def match(S, P):
  for i in range(len(S) - len(P) + 1):
    if S[i:i+len(P)] == P:
      return i

如果 n = len(S), m = len(P)。那么最坏的情况下，暴力解法的时间复杂度能去到O(nm)。

暴力解法并没有利用字符串匹配过程中残留的一部分信息，而KMP算法则是通过“尽可能减少比较的趟数”来做到优化，即看看能否在匹配失败后，跳过一部分不可能成功的字符串比较来使复杂度降低。

简述KMP起始思路