动态规划解KMP算法
KMP算法是一个非常经典的字符串匹配算法，效率很高，其原因也在于使用了动态规划的设计思想，但是着实复杂。。为了更加便于理解，本文采用的是一种二维dp数组的方式，而不是一般资料里非常神奇的一维数组（水平有限，菜），但是问题的复杂度并没有上升。下面看问题描述：
pat 表示模式串，长度为 M，txt 表示文本串，长度为 N。KMP 算法是在 txt 中查找子串 pat，如果存在，返回这个子串的起始索引，否则返回 -1。问题倒是很简单，如果用暴力算法解决，时间复杂度则是 $$ O(M*N)$$, 显然不现实。在解决这个问题的过程中，我发现这个问题对状态分析的过程非常经典，其他资料更加直接，直接使用DFA来解决这个问题。在我看来动态规划和DFA有着异曲同工之妙，也可以说本题就是DFA的代码实现，其他类似问题完全可以套用。废话不多说，下面开始分析。
1. 确定问题的状态与dp数组
在暴力解法中，影响时间复杂度的最大原因就是搜索指针只是在盲目的穷举所有的情况，其中包括一些没有意义的情况。如果能解决这个问题，那么算法的时间复杂度就会很大的提高。
对于pat和txt来说，pat是固定的，而txt却是任意的。他们的共同点就是要在txt里匹配出pat，因此我们选择用相对固定的pat来设计有限的状态（好吧其实是书上说要用DFA的我也不太明白为啥就不瞎BB了）。
回想计算理论学习的DFA设计正规文法，我们可以用类似的思路来设计这个问题的状态。即按照pat的字符串的顺序,每一个字符都是一个状态(即当txt每多匹配一个字符，就是一个不同的状态)。那么按照这个思路，dp数组里记录的就是各个状态之间的转移关系了。要确定状态转移的行为，得明确两个变量，一个是当前的匹配状态，另一个是遇到的字符。因此，我们定义dp数组为：dp[j][c] = next，其中j代表当前状态，C代表当前的字符（用asc码表示，或者用字典实现）。举例来说，dp[4]['A'] = 3含义就是，在状态4时，匹配到了字符A，于是要跳转到状态３即可。有了这个定义，我们可以很容易的实现搜索操作。
2. 明确当前的选择
从暴力解法来看，如果当前字符c和pat[i]是匹配的，那就转移到下一个状态；如果不匹配，那么就转移到另一个状态。因此选择就是根据当前字符串c进行状态的转移。
3. 构建状态方程（DFA）
在前面的分析中，当c和pat[i]不匹配时，我们说应该转移到另一个状态，那么这个状态到底应该如何确定呢？
这里就涉及到一个编程的小技巧。当遇到不匹配的情况时，搜索指针就要进行回退，在暴力算法中会同时回退pat指针和txt指针。为了减少时间复杂度，我们可以利用dp数组中存储的信息，来确定回退的具体位置。具体来说，就是用一个变量来记录当前状态的上一个相同前缀的状态即可，记为X。当前状态如果不能匹配的话，就去询问状态X ，应该如何跳转即可。因为状态X在之前已经计算过了（动态规划）。
4. base case分析
本问题中，当任何字符都没有匹配的时候，我们设定为状态0，那么在状态0下，只有匹配到pat的第一个字符才能继续推进状态，即base case就是dp[0][pat[0]]=1;
5. 代码实现
下面给出具体的完整代码：
class KMP:
def __init__(self, pat: str):
self.pat = pat
M = len(pat)
self.dp = [[0] * 256 for _ in range(M)]
self.dp[0][ord(pat[0])] = 1
X = 0
for j in range(1, M):
# for c in range(256):
# if ord(pat[j]) == c:
# self.dp[j][c] = j+1
#else:
# self.dp[j][c] = self.dp[X][c]
#X = self.dp[X][ord(pat[j])]
for c in range(256):
self.dp[j][c] = self.dp[X][c]
self.dp[j][ord(pat[j])] = j+1
X = self.dp[X][ord(pat[j])]
def search(self, txt: str):
M = len(self.pat)
N = len(txt)
j = 0
for i in range(N):
j = self.dp[j][ord(txt[i])]
if j == M:
return i - M + 1
return -1
