【GOOGLE2013校招第3道大题】
2.3 给定一个原串和目标串，只能对源串进行如下操作：
1.在给定位置插入一个字符
2.替换任意字符
3.删除任意字符
要求写一个程序，返回最少的操作数，使得源串进行这些操作后等于目标串。源串和目标串长度都小于2000。（只需设计思路和关键步骤伪代码）
分析：其实是考察字符串相似算法中的DL算法。
1 字符串相似度算法应用
字符串相似算法用来描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。主要的算法有基于最小编辑距离（Edit Distance）的LD算法（时间复杂度为O(mn)）和最长公共子序列算法（时间复杂度为O(mn)）。其应用如，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。如判断S1和S2相似的办法是找出他们的公共子序列S3，S3以相同的顺序在S1和S2中出现，但是不必要连续。S3越长，S1和S3就越相似。
搜索引擎中有着重要的作用，最常用的是拼写错误检查，如搜索引擎关键字查询中拼写错误的提示，可以用上述2个算法计算字符串直接的相似度。Google的拼写错误检查的原理是什么呢？Google是基于贝叶斯统计推断的方法，相关原理详情可以看下Google的研发总监Peter
Norvig写的文章，以及fuanyif写的博客“贝叶斯推断及其互联网应用”，介绍用贝叶斯算法过滤垃圾邮件。关于贝叶斯算法的理论可以参考微软刘未鹏的“数学之美番外篇：平凡而又神奇的贝叶斯方法”。
2 最长公共子序列算法
问题描述
最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。
题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子序列。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子序列，并打印出最长公共子序列。
例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，则输出它们的长度4，并打印任意一个子串。
用动态规划解决
2.1 描述一个最长公共子序列（描述最优解的结构）
先介绍LCS问题的性质：记Xm={x1,…xm}和Yn={y1,…,yn}为两个字符串，而Zk={z0,z1,…zk}是它们的LCS，则：
1） 如果xm=yn，那么zk=xm=yn，并且Zk-1是Xm-1和Yn-1的一个LCS；
2）如果xm≠yn，那么当zk≠xm时Zk-1是Xm-1和Y的一个LCS；
3）如果xm≠yn，那么当zk≠yn时Zk-1是Yn-1和X的一个LCS；
证明略见《算法导论》
2.2递归定义最优解的值
有了上面的性质，我们可以得出如下的思路：求两字符串Xm={ x1,…xm}和Yn={y1,…,yn}的LCS，如果xm=yn，那么只需求得Xm-1和Yn-1的LCS，并在其后添加xm（yn）即可；如果xm-1≠yn-1，我们分别求得Xm-1和Y的LCS和Yn-1和X的LCS，并且这两个LCS中较长的一个为X和Y的LCS。
记字符串Xi和Yj的一个LCS的长度为c[i,j]。如果i=0或j=0，其中一个的长度为0，因此LCS的长度为0。由LCS问题的最优子结构可得递归式：
/ 0 if i<=0 or j<=0
c[i,j]= c[i-1,j-1]+1 if i,j>0 and xi=yj
\ max(c[i,j-1],c[i-1,j] if i,j>0 and xi≠yj
2.3 计算LCS的长度（按自底向上的方式计算最优解的值）
上面的公式用递归函数不难求得。但直接递归（自顶向下）会有很多重复计算，我们用从底向上循环求解的思路效率更高。
为了能够采用循环求解的思路，我们用一个矩阵c[0..m,0..n]保存下来当前已经计算好了的c[i,j]，当后面的计算需要这些数据时就可以直接从矩阵读取。另外，求取c[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到，相当于在矩阵c[0...m,0...n]中是从c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j]，因此在矩阵中有三种不同的移动方向：向左、向上和向左上方，其中只有向左上方移动时才表明找到LCS中的一个字符(因为c[i-1,j-1]+1
，if i,j>=0 and xi=xj)。于是我们需要用另外一个矩阵b[1..m,1..n]保存移动的方向。
下面是计算字符串Xm={ x1,…xm}和Yn={y1,…,yn}的LCS的长度伪代码：
LCS-LENGTH(X,Y)
m <- length[X]
n <- length[Y]
//i=0 或 j=0
for i <- 0 to m
do c[i,0]= 0
for j <- 0 to n
do c[0,j]= 0
for i=1 to m
do for j=1 to n
do if xi=yj //c[i,j]=c[i-1,j-1]+1 ,if i,j>=0 and xi=xj
then c[i,j]=c[i-1,j-1]+1
b[i,j]="左上方箭头"
else if c[i,j-1]>=c[i-1,j] //max(c[i,j-1],c[i-1,j] ,if i,j>=0 and xi≠xj
then c[i,j]=c[i,j-1]
b[i,j]="左方箭头"
else c[i,j]=c[i-1,j]
b[i,j]="上方箭头"
return c and b
算法时间复杂度O(mn)
具体例子图见《算法导论》P211
2.4 由计算出的结果构造一个最优解
Print-LCS(b,X,i,j)
if i=0 或 j=0
then return
if b[i,j]="左上方箭头"
then Print-LCS(b,X,i-1,j-1)
else if b[i,j]="上方箭头"
then Print-LCS(b,X,i-1,j)
else Print-LCS(b,X,i,j-1)
3 LD(Levenshtein distance)最小编辑距离算法
3.1 描述最优子结构
如果X与Y的第一个字符不相同，那么可以进行如下操作：
3）删除X的第一个字符，然后计算X[2,...,M]和Y[1,...,N]的距离；
j]表示源字符串[1..i]到目标字符串[1..j]之间的最小编辑距离。则最优子结构可以描述为
当 xi≠yj时，LD[i,j]=min(LD[i-1,j-1]+1,LD[i-1,j]+1,LD[i,j-1]+1)
- 1, j - 1] + 1表示对source[i]替换成target[i]操作后计算最小编辑距离
j - 1] + 1 表示对source[i]执行插入操作后计算最小编辑距离
- 1, j] + 1 表示对source[i]执行删除操作后计算最小编辑距离
/ i if j=0
j if i=0
if i,j>0 and xi=yj
\ min(LD[i-1,j-1],LD[i-1,j],LD[i,j-1])
if i,j>0 and xi≠yj
- 1, j - 1] + 1表示对source[i]替换成target[i]操作后计算最小编辑距离
j - 1] + 1 表示对source[i]执行插入操作后计算最小编辑距离
- 1, j] + 1 表示对source[i]执行删除操作后计算最小编辑距离
3.3 按自底向上方式计算最优解的值
为了能够采用循环求解的思路，我们用一个矩阵LD[0..m,0..n]保存下来当前已经计算好了的LD[i,j]，当后面的计算需要这些数据时就可以直接从矩阵读取。另外，求取LD[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到，相当于在矩阵LD[0...m,0...n]中是从LD[i-1,j-1]，LD[i,j-1]或者LD[i-1,j]的某一个各自移动到LD[i,j]，因此在矩阵中有三种不同的移动方向：向左、向上和向左上方，于是我们需要用另外一个矩阵b[1..m,1..n]保存移动的方向。
下面是计算字符串Xm={ x1,…xm}和Yn={y1,…,yn}的LD的长度伪代码：
LengthEdit(x,y){
m=x.length;
n=y.length;
//初始化LD数组(即i=0或j=0)
for j=0 to n
LD[0,j]=j;
for i=0 to m
LD[i,0]=i;
//自底向上构造最优解
for i=1 to m{
for j=1 to n{
if(x[i]=y[j]){
LD[i,j]=LD[i-1,j-1];
}//end if
else{
LD[i,j]=min(LD[i-1,j-1]+1,LD[i-1,j]+1,LD[i,j-1]+1);
}//end else
}//end for
}//end for
return LD;
}//end LengthEdit()
//获取最小值
min(LD[i-1,j-1],LD[i-1,j],LD[i,j-1])(
minVlaue //用于存放最小值
if(LD[i-1,j-1]> LD[i-1,j]){
if(LD[i-1,j]>LD[i,j-1]){
minValu=LD[i,j-1];
b[i,j]="左方箭头";
}//end if
else{
minValu=LD[i-1,j];
b[i,j]="上方箭头";
}//end else
else{ //LD[i-1,j-1]< LD[i-1,j]
if(LD[i-1,j-1]>LD[i,j-1]){
minValu=LD[i,j-1];
b[i,j]="左方箭头";
}//end if
else{
minValu=LD[i-1,j-1];
b[i,j]="左上方箭头";
}//end else
}//end esle
}//end if
return minValue;
)//min()
3.4 由计算出的结果构造一个最优解
Print-LD(b,X,i,j)
if i=0 或 j=0
then return
if b[i,j]="左上方箭头"
then Print-LD(b,X,i-1,j-1) //c[i-1,j-1],替换操作
else if b[i,j]="上方箭头"
then Print-LCS(b,X,i-1,j) //c[i-1,j],删除查找
else Print-LCS(b,X,i,j-1) //c[i,j-1],插入操作
Lucene中也有这个算法的实现(一般的搜索引擎一般都应该会有此项拼写错误检查功能的实现)，下面是lucene的源码：
//--------------------------------------------------------------------------------------------
public final class LevensteinDistance {
public LevensteinDistance () {
}
// Compute Levenshtein distance:
// see org.apache.commons.lang.StringUtils#getLevenshteinDistance(String, String)
public float getDistance (String target, String other) {
char[] sa;
int n;
int p[];
//'previous' cost array, horizontally
int d[];
// cost array, horizontally
int _d[];
//placeholder to assist in swapping p and d
sa = target.toCharArray();
n = sa.length;
p = new int[n+1];
d = new int[n+1];
final int m = other.length();
if (n == 0 || m == 0) {
if (n == m) {
return 1;
}
else {
return 0;
}
}
// indexes into strings s and t
int i;
// iterates through s
int j;
// iterates through t
char t_j;
// jth character of t
int cost;
// cost
for (i = 0; i<=n; i++) {
p[i] = i;
}
for (j = 1; j<=m; j++) {
t_j = other.charAt(j-1);
d[0] = j;
for (i=1; i<=n; i++) {
cost = sa[i-1]==t_j ? 0 : 1;
// minimum of cell to the left+1, to the top+1, diagonally left and up +cost
d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost);
}
// copy current distance counts to 'previous row' distance counts
_d = p;
p = d;
d = _d;
}
// our last action in the above loop was to switch d and p, so p now
// actually has the most recent cost counts
return 1.0f - ((float) p[n] / Math.max(other.length(), sa.length));
}
}
//--------------------------------------------------------------------------------------
最长公共子串见博客：动态规划：最长公共子串
参考文献
[4]
最大连续乘积子串、字符串编辑距离 http://blog.csdn.net/v_july_v/article/details/8701148(关于字符串相似度的应用将的比较好)