常见算法题之字符串

1、KMP算法

参考：july大神的KMP博客
细节不摆，该算法由暴力字符串来匹配，具体是由字符串匹配的暴力写法而来。

优化点：

减少子串的回溯步长，从而优化时间复杂度。
关键点：

• Q: 根据什么可以减少子串的回溯步长呢？
  A: 就是根据当前不匹配的字符位置之前的子字符串的“相同前后缀”的特征，使得子串移动到前一个可能匹配的位置。
• Q: 如何获得每个字符“之前的子字符串的相同前后缀的特征”呢？
  A: 通过预处理子串，获得一个next数组，表示每个位置前的子字符串的最大公共前后缀长度。
• Q: next数组如何计算得来？
  A: 通过两个动态规划的特点，计算得来：
  如果对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于next[j] = k
  第一， 若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
  第二， 若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, ..., k, ..., j]）进行P串前缀跟P串后缀的匹配。