KMP

KMP是一种高效的字符串匹配算法

你仔细观察的话，不难发现，KMP算法选择了一个相当巧妙的位置进行了移动。

而KMP算法的核心就是寻找这个巧妙的位置，我们把这个位置存储在一个数组里，一般把这个数组命名为next数组，寓意为匹配失败后，待匹配的字符串应该移动到的下一个位置。

倘若遮住原来匹配失败的字母A和C和他们右边的所有内容，只告诉你匹配失败了，让你寻找下一个可能匹配成功的位置，那么你肯定会做出和KMP算法一样的移动方式，即找到’DCBD’的后缀中和’BDCBD’的前缀中相同部分最多的那个位置。而我们已经知道在匹配失败的字母A和C前的字母是匹配成功的，即’BDCBD’=‘BDCBD’，那么其实就是找待匹配字符串中失配字母的前面部分，使得前缀和失配字母的前缀相同，且相同的位数最多的那个字母。

说白了，求KMP的next数组，就是待匹配的字符串自己与自己匹配的艺术

下面就给出求’BDCBDA’这个字符串的next数组的过程

假设next[i] = k, 那么就说明第i个字母的前面k个字母与字符串的前k个字母是相同的。假设字符串的第i个字母与第k+1个字母是相同的，那么显然有next[i + 1] = k + 1；如果这两个字母不同呢，我们再假设next[k] = m ,即第k个字母的前面m个字母与字符串的前m个字母是相同的，那么字符串的前m个字母就与第i个字母的前面m个字母是相同的，再继续判断第i个字母是否与第m+1个字母相同…直到得到答案为止，或者已经递推到了第一个字母。

倘若你对上面的讲解已经没有了疑问，那么你已经具备独立写出KMP算法的能力了，快去上机试试吧！

KMP算法的next数组还可以进一步的优化，感兴趣的同学可以自行在网上学习哦

Hash

Q：给定 N个字符串，求出这 N个字符串*有多少个不同的字符串？

A：你可能会这样想：把每个字符串与之前所有的字符串比较，看是否有相同的字符串，没有则总数+1，有则拿下一个字符串进行相同的操作。

但当字符串很长的时候，我们很容易发现这样暴力的去比较，效率实在是太低了，因为每次比较字符串总需要一个字母一个字母的比较。而字符串哈希则很好的解决了这个问题：倘若我们能建立一个从字符串到数值的映射，那么我们的问题就变成了N个数值中有多少个不同的数，问题就大大简化了。

相信你一定知道16进制，里面除了0-9，还有A-F几个字母。就是说一个字符串’ABC’在16进制里可以理解成一个数字。那么同样的，只要进制够大，我们就可以把任何一个字符串都看成是一个数字，这样字符串到数值的映射就完成了。

Manacher

回文串是一种美丽的字符串。

而Manacher算法（马拉车算法????），就是一种用来寻找一个字符串中最长回文子串的高效算法。

一个回文串的长度可能是奇数，也可能是偶数。我们很容易发现奇回文串会有一个最中点（我们把这个中点称作回文中心），而偶回文串则没有。而Manacher算法是一种基于回文中心的一种算法。因此我们首先需要对字符串进行处理：我们都知道n + (n + 1)无论如何都是一个奇数，和 n 的奇偶性无关。我们就可以通过在字符串的开头和结尾，以及每两个字符中间插入一个相同的特殊字符，那么奇回文串和偶回文串都变成了奇回文串，并且新的字符串回文中心到边界的距离（我们称之为回文半径）便是原来字符串的长度，如’1221’变成了’#1#2**#**2#1#’，边界到回文中心的距离恰好为4；如’12321’变成了’#1#2#3#2#1#’，边界到回文中心的距离恰好为5。

对字符串进行预处理后，我们该如何利用回文中心的概念来求出任意一个字符串中的最长回文子串呢？

倘若我们已知了一个回文中心的回文半径，要求这个点之后的某一点的回文半径，倘若要求的点到回文中心的距离小于回文中心的回文半径，那么可能会出现三种情况（还有一种R2=R3）

根据回文串的对称性质，我们很容易发现当前点的回文半径，与对称点的回文半径R2，以及当前点到边界的距离R3有着很大的关系。倘若R2<R3的话，显然当前点的回文半径就是R2；倘若R2>R3的话，那么当前点回文半径就是R3（因为左边界的左边一点和右边界的右边一点一定是不同的，否则对称中心的回文半径就不是R1了）；倘若R2=R3的话，那么当前点的回文半径就至少为R3，之后再以当前点为中心向两端扫描，倘若两个字母相同，则回文半径+1，直到不同为止。

我们在扫描过程中如何去更新回文中心呢？只要我们通过当前回文中心求得的某一点的右边界超出了当前的右边界，我们便可用该点来作为下一个回文中心。

每次求得回文中心后紧接着求它下一点的回文半径，倘若下一点的右边界为超出当前回文中心的右边界，我们便继续往后扫描，直到需要更新回文中心，然后重复上述步骤直到扫描完整个字符串。这个过程中，我们每一次求出回文半径便将它记录下来，最终便可得到最长回文半径。

快去上机试试吧！

如果您觉得我的文章对您有帮助的话，可以点个赞，点个关注，也可以扫描下方二维码关注我。我将在这个公众号上更新自己的学习笔记，以及分享一些算法知识

Study and progress together with me!