字符串相关算法

在前面的章节我们已经学习过如何使用字符串，比如字符串的查找，匹配，拼接，分割等，也学过正则表达式查找。在这一节中，将详细讲述这些实现的一些底层技术，从另一个角度去认识字符串。

1. 字符串子串查找算法KMP

给定一个主串（以 S 代替）和模式串（以 P 代替），要求找出 P 在 S 中出现的位置，此即串的模式匹配问题。

Knuth-Morris-Pratt 算法（简称 KMP）是解决这一问题的常用算法之一，这个算法是由高德纳（Donald Ervin Knuth）和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表。

KMP算法与其他字符串子串查找的典型的区别是它先计算子串本身存在的一些相关信息，这样可以保证每次匹配不用从最开始位置查找，而是从最佳的位置开始匹配，从而提高了查找的效率，保证复杂度在O(n+m)规模。KMP算法的精华部分就在于求模式匹配的next数组，如果对状态机有所了解，就能很好的理解这一思想。

由于关于KMP算法网上有很多经典的的介绍，这里就不详细讨论，只给出算法实现。

代码实现：

class Solution: def getnext(self,needle): needleLen=len(needle) next=[-1]*needleLen i,k=0,-1 while i

2.最长连续公共子序列

要求两个字符串的最长连续公共子序列，一般采用的方法是后缀数组法，即先分别求出两个串的后缀数组，然后比较它们之间的连续公共长度。这个有个处理技巧就是为了确认哪个后缀数组属于哪个串，需要在其中一个串后面贴一个标签，避免混淆。

当然另一种是使用动态规划进行求解，因此求出问题的状态转移方程至关重要。下面是求解最长连续公共子序列的状态转移方程，知道了状态转移方程，求解就变得很简单了。

代码实现：

class Solution: def ConsecutiveLCS(self,s1,s2): s1Len=len(s1) s2Len=len(s2) arr=[[0]*(s2Len+1) for i in range(s1Len+1)] res=0 for i in range(1,s1Len+1): for j in range(1,s2Len+1): if s1[i-1]==s2[j-1]: arr[i][j]=arr[i-1][j-1]+1 if res

3.最长公共子序列

要求两个串的公共子序列，则这些子序列不一定是连续的，如下图所示。

对于这类问题通常的解法是采用动态规划，状态转移方程如下所示。

代码实现：

class Solution: def LCS(self,s1,s2): s1Len=len(s1) s2Len=len(s2) arr=[[0]*(s2Len+1) for i in range(s1Len+1)] for i in range(1,s1Len+1): for j in range(1,s2Len+1): if s1[i-1]==s2[j-1]: arr[i][j]=arr[i-1][j-1]+1 else: arr[i][j]=max(arr[i-1][j],arr[i][j-1]) return arr[s1Len][s2Len]

4.字符串模糊匹配（状态机）

对字符串进行模糊匹配查找，我们通常采用的是正则表达式实现。在很多文本编辑器里，正则表达式通常被用来检索、替换那些匹配某个模式的文本。

而如何判断一个字符串与当前的正则表达式匹配，一般是将一个正则表达式转化为一个状态机。当当前的字符串在匹配过程中进入一个可接受状态，则称之为匹配成功。

正则表达式a(bb)+a的状态转移图

每一个正则表达式都有一个对应的有限状态机。然而这个对应的有限状态机可能是确定的，也可能是非确定的。非确定状态机和确定状态机的区别是对于一个接收符号是否有唯一的离开路径，如果离开路径唯一则是确定的，否则为非确定的。对于非确定有限状态机（如下图所示），一般存在多路径匹配，而对于确定有限状态机（如上图所示）则不会。

非确定状态机多路径匹配

因此，如果对非确定有限状态机不想采用多路径匹配，一种通常的处理思路是采用子集构造算法将非确定状态机转为有限状态机。由于涉及的相关知识较多，有兴趣可以参阅相关正则表达式算法实现或者词法分析进行详细了解。

例：判断一个字符串是否是一个实数。

测试样例：

"0" => true" 0.1 " => true"abc" => false"1 a" => false"2e10" => true

分析：根据题意，可以写出实数判定的正则表达式：(\s*)[+-]?((\.[0-9]+)|([0-9]+(\.[0-9]*)?))(e[+-]?[0-9]+)?(\s*)。然后将它转为一个状态机进行求解，如下图所示。

代码实现：

class Solution: def isNumber(self, s): """ :type s: str :rtype: bool """ s=s.strip() sLen=len(s) if sLen

5.编辑距离算法

编辑距离，又称Levenshtein距离（莱文斯坦距离也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

在概念中，我们可以看出一些重点那就是，编辑操作只有三种。插入，删除，替换这三种操作，我们有两个字符串，将其中一个字符串经过上面的这三种操作之后，得到两个完全相同的字符串付出的代价是什么就是我们要讨论和计算的。在这里我们设置每经过一次编辑，也就是变化（插入，删除，替换）我们花费的代价都是1。

编辑距离的作用主要是用来比较两个字符串的相似度的。

对于这类问题，我们可以采用动态规划进行解决：用f[m-1,n]+1表示增加操作，f[m,n-1]+1 表示我们的删除操作，f[m-1,n-1]+temp（str1[i] == str2[j]，用temp记录它，为0；否则temp记为1）表示我们的替换操作。状态转移方程为：

代码实现：

class Solution: def EditDistance(self,s1,s2): s1Len=len(s1) s2Len=len(s2) arr=[[0]*(s2Len+1) for i in range(s1Len+1)] for i in range(s1Len+1): arr[i][0]=i for i in range(s2Len+1): arr[0][i]=i for i in range(1,s1Len+1): for j in range(1,s2Len+1): tmp=1 if s1[i-1]==s2[j-1]: tmp=0 arr[i][j]=min([arr[i][j-1]+1,arr[i-1][j]+1,arr[i-1][j-1]+tmp]) return arr[s1Len][s2Len]