字符串的算法很多，下面讨论几个比较典型的与字符串匹配有关的算法。

1.LCS最长公共子序列

字符串的子序列是指从该字符串中删除一些字符（可以不删除），保持字符之间的相对位置不变，而得到的字符串；$A,B$之间的最大公共子序列是指求出$A,B$相同的子序列中，长度最长的那个。

输入：两个字符串$A,B$，长度为$m,n$

输出：字符串$A,B$的最长公共子序列

思路：这是动态规划的典型的应用，在LCS问题中，最优子结构可以通过在字符串右边删除字符得到一个子问题，而且这个子问题的最优解是整体最优解的一部分。这里简单讨论一下：我们设$Z$(长度为$k$)为$A,B$的一个LCS，那么我们就可以分为三种情况：如果$A_m=B_n$,那么这样我们就可以说$Z_k=A_m=B_n$，而且$Z(1,2,...,k-1)$是$A(1,2,..,m-1),B(1,2,...,n-1)$的最长公共子序列。用反证法很容易证明，如果$Z_k!=A_m$,可以将$A_m$添加到$Z$上，得到一个长度为$k+1$的子序列，这与$Z$是LCS就矛盾了；如果$Z(1,2,...,k-1)$不是$A(1,2,..,m-1),B(1,2,...,n-1)$，那么假设存在一个长度大于$k-1$的子序列，然后将$A_m$添加到该子序列上，显然子序列长度大于$K$,这与$Z$是LCS也矛盾了。当$A_m!=B_n$是，我们可以比较$A_m$与$B_{n-1}$或是$A_{m-1}$与$B_n$的LCS,然后将大的作为LCS。用反证法也可以证明。这时候子问题在构造的时候进行了“删除”，只选择那些最大的就OK。

递归式：

\[
C(i,j)=\begin{cases}
0 & \text { if }  i=j=0 \\ 
C(i-1,j-1)+1 & \text{ if } i,j> 0,A_i=B_j \\ 
max\{C(i-1,j),C(i,j-1)\} & \text{ if } i,j>0,A_i\neq B_j
\end{cases}
\]

这样我们就可以使用一个二维表格存储子问题的解，然后逐渐有递归式子求出问题的解。这也是动态规划解决问题的一般过程，把中间结果存储，避免重复计算，降低复杂性。

代码如下：

public static int[][] lcs_length(char[] x, char[] y) {
		int m = x.length;
		int n = y.length;
		int[][] b = new int[m + 1][n + 1];
		int[][] c = new int[m + 1][n + 1];
		int i;
		int j;
		for (i = 0; i <= m; i++)
			c[i][0] = 0;
		for (j = 0; j <= n; j++)
			c[0][j] = 0;
		for (i = 1; i <= m; i++)
			for (j = 1; j <= n; j++) {
				if (x[i - 1] == y[j - 1]) {
					c[i][j] = c[i - 1][j - 1] + 1;
					b[i][j] = 0;
				} else if (c[i - 1][j] >= c[i][j - 1]) {
					c[i][j] = c[i - 1][j];
					b[i][j] = 1;
				} else {
					c[i][j] = c[i][j - 1];
					b[i][j] = 2;
				}
			}
		return b;
	}

代码 优化：上面的代码可以进行“空间优化”，比如数组b可以只用两行就行；数组c可以省略，可以根据b来判断从而得到子序列（这时候b就不能只用两行了。。。）

复杂性分析：从上面的代码容易得出，复杂性为$O(mn)$。

2.编辑距离

字符串A,B 的编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数,这里的合法编辑操作包括插入，删除和替换一个字符。

输入：两个字符串$A,B$，长度为$m,n$

输出：字符串$A,B$的编辑距离

思路：编辑距离与上面的LCS问题非常相似,也是一个动态规划问题。子问题的构造方式差别不大，也是从字符串右面开始，构造子问题，在采取添加，删去，替换操作后，分别转化到三个不同的子问题，然后选择这三个中最小的作为最优的子问题的解，用来构造下面的解。若是在$A$末尾插入一个字符，则$d(m,n)$必定是$A(1,2,...,m-1),B(1,2,..,n)$的编辑距离$d(m-1,n)$加$1$。采用反证法很容易证明：若$A(1,2,...,m-1),B(1,2,..,n)$存在比$d(m-1,n)$小的编辑距离，那么在A末尾插入一个字符后，该编辑距离要比$d(m,n)$小，这就与$d(m,n)$是编辑距离矛盾了。其他两种情况类似，这样就说明了最优子结构。

递归式：

\[
d(i,j)=\begin{cases}
max\{i,j\} & \text{ if } min\{i,j\}=0 \\ 
min\{d(i,j-1)+1,d(i-1,j)+1,d(i-1,j-1)+cost(i,j)\}& \text{ otherwise }
\end{cases}
\]

其中，

\[
cost(i,j)=\begin{cases}
0 & \text{ if } A_i=B_j\\ 
1& \text{ if } A_i\neq B_j 
\end{cases}
\]

代码如下：

public int editDistance(String a,String b){
		int m=a.length();
		int n=b.length();
		int [][] t=new int[m+1][n+1];
		int cost=0;
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++){
				if(a.charAt(i-1)==b.charAt(j-1))
					cost=0;
				else
					cost=1;
				t[i][j]=Math.min(t[i-1][j]+1,Math.min(t[i][j-1]+1,t[i-1][j-1]+cost));
			}
		return t[m][n];
	}

3.字符串匹配

字符串匹配：探测一个模式子序列在文本字符串中出现的位置。这是一个经常使用的操作，非常频繁，几乎任何编辑器都支持。
输入：给定模式字符串P和文本字符串T，长度分别为m,n

输出：如果P在T中，给出P在T中出现的位置，如果不在，返回-1

思路：一种自然的想法就是从T的第一个位置开始匹配p,若不成功，则从第二个位置匹配下去，一直到(m-n+1)位置，如果我们要匹配多个位置，则输出全部符合的即可；若没有匹配成功的，则输出-1。匹配算法有很出名的KMP算法，即Knuth-Morris-Pratt Algorithm，可以在线性时间内完成匹配。KMP的思想就是借助模式子序列本身的性质（模式子序列的前缀子序列），利用已经匹配的模式，减少匹配次数。

比较难理解的就是如何借助模式子序列的性质，来减少匹配次数。

如下面的图所示，在j位置已经匹配到了T中的i位置，那么我们就可以假设i前面已经有k个字符被匹配，也就是T[i-k,i]=P[j-k,j]，这时候下一个位置已经不匹配了，这时候如果我们知道P[0,k]=P[j-k,j]的一个最大值，既可以跳过前面k个字母，直接从p[k+1]和T[i+1]开始比较，这样的模式串的移动速度就加快了。所以我们使用一个辅助的数组lps，其中lps[i]值得含义是：模式串前i中，前缀和后缀匹配的最大长度。在求解lps数组值得时候，又是一个子序列自我匹配的过程，在线性时间内完成。

代码如下：

public int [] lps(String p){
		int m=p.length();
		int [] l=new int[m];
		//l[0] is always zero
		l[0]=0;
		int len=0;
		//computer l[1,2,...,m-1]
		int i=1;
		while(i<m){
			if(p.charAt(len)==p.charAt(i)){
				len++;
				l[i]=len;
				i++;
			}
			else{
				if(len!=0){
					len=l[len-1];
				}
				else{
					l[i]=0;
					i++;
				}
			}
		}
		return l;
	}

	public void kmp(String p,String t){
		int [] lp=this.lps(p);
		int i=0;
		int j=0;
		int m=p.length();
		int n=t.length();
		while(j<n){
			if(p.charAt(i)==t.charAt(j)){
				i++;
				j++;
			}
			if(i==m){
				System.out.println(j-i);
				i=lp[i-1];
			}
			else if(p.charAt(i)!=t.charAt(j)){
				if(i!=0){
					i=lp[i-1];
				}
				else{
					j++;
				}
			}
		}
	}

参考：

[1]字符串匹配

[2]算法导论，课件