kmp算法是否属于动态规划？

Question

在网上看到一条KMP题解，里面说到KMP是动态规划算法，但我以前问过动态规划的无后效性问题，简单总结无后效性要么是后者的状态对前者的状态有多种选择，要么就是后者的状态是不可改变的。但是KMP的核心是后缀找相同前缀，那么状态也就只能定义成某个字符有多少个相同前缀，所以状态是单一可变的，所以我个人看法是KMP并不属于动态规划，不知道是否理解有误，有的话请bobo老师指出：）

Answer 1

liuyubobobo 2020-02-05 03:07:59

kmp 算法分成两部分。

第一部分是求解一个辅助的匹配数据结构，比如你说的题解中，无论是求解 next 数组还是求借这个 dfa，都是这部分。这部分可以理解成动态规划。

第二部分是具体的利用这个辅助数据做匹配，这部分不是动态规划。

不过整体，通常不会把 kmp 和动态规划联系起来。说实话，将这种经典算法和算法思想联系起来，是挺虚的，我个人认为并不有助于理解经典算法本身。比如 Prim 算法背后有贪心的思想，但是了解这一点并不会让你对 Prim 理解的更深刻；Dijkstra 背后既有贪心的思想，又有动态规划的思想，同样，我不认为了解这一点会让你对 Dijkstra 理解的更深刻：）

继续加油！：）

• 提问者 哈哈哈蜜瓜 #1

  问题在于next数组为什么可以看成动态规划，按无后效性的原则那应该怎样定义状态体现它的无后效性呢

• liuyubobobo 回复 提问者 哈哈哈蜜瓜 #2

  我一般不习惯叫 next，而习惯叫 lps，即 longest proper prefix。lps[i] 表示 s[0...i] 中的最长的和前缀相同的后缀。lps[i] 完全可以被 lps[0...i-1] 中的信息推导出。lps[i] 的大小不影响 lps[i + 1...n) 的大小。

• 提问者 哈哈哈蜜瓜 回复 liuyubobobo #3

  想了一下想通了，感谢老师：）