最长公共子串（LCS）
找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧："bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")
b a b
c 0 0 0
a 0 1 0
b 1 0 1
a 0 1 0
我们看矩阵的斜对角线最长的那个就能找出最长公共子串。
不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。
b a b
c 0 0 0
a 0 1 0
b 1 0 2
a 0 2 0
这样矩阵中的最大元素就是 最长公共子串的长度。
在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。
代码如下：
#include<iostream> #include<cstring> #include<vector> using namespace std; //str1为横向，str2这纵向 const string LCS(const string& str1,const string& str2){ int xlen=str1.size(); //横向长度 vector<int> tmp(xlen); //保存矩阵的上一行 vector<int> arr(tmp); //当前行 int ylen=str2.size(); //纵向长度 int maxele=0; //矩阵元素中的最大值 int pos=0; //矩阵元素最大值出现在第几列 for(int i=0;i<ylen;i++){ string s=str2.substr(i,1); arr.assign(xlen,0); //数组清0 for(int j=0;j<xlen;j++){ if(str1.compare(j,1,s)==0){ if(j==0) arr[j]=1; else arr[j]=tmp[j-1]+1; if(arr[j]>maxele){ maxele=arr[j]; pos=j; } } } // { // vector<int>::iterator iter=arr.begin(); // while(iter!=arr.end()) // cout<<*iter++; // cout<<endl; // } tmp.assign(arr.begin(),arr.end()); } string res=str1.substr(pos-maxele+1,maxele); return res; } int main(){ string str1("21232523311324"); string str2("312123223445"); string lcs=LCS(str1,str2); cout<<lcs<<endl; return 0; }
最长公共子序列
最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的，比如ADE和ABCDE的最长公共子序列是ADE。
我们用动态规划的方法来思考这个问题如是求解。首先要找到状态转移方程：
符号约定，C1是S1的最右侧字符，C2是S2的最右侧字符，S1‘是从S1中去除C1的部分，S2‘是从S2中去除C2的部分。
LCS(S1,S2)等于下列3项的最大者：
（1）LCS（S1，S2’）
（2）LCS（S1’，S2）
（3）LCS（S1’，S2’）--如果C1不等于C2； LCS（S1‘，S2‘）+C1--如果C1等于C2；
边界终止条件：如果S1和S2都是空串，则结果也是空串。
下面我们同样要构建一个矩阵来存储动态规划过程中子问题的解。这个矩阵中的每个数字代表了该行和该列之前的LCS的长度。与上面刚刚分析出的状态转移议程相对应，矩阵中每个格子里的数字应该这么填，它等于以下3项的最大值：
（1）上面一个格子里的数字
（2）左边一个格子里的数字
（3）左上角那个格子里的数字（如果 C1不等于C2）； 左上角那个格子里的数字+1（ 如果C1等于C2）
举个例子：
G C T A
0 0 0 0 0
G 0 1 1 1 1
B 0 1 1 1 1
T 0 1 1 2 2
A 0 1 1 2 3
填写最后一个数字时，它应该是下面三个的最大者：
（1）上边的数字2
（2）左边的数字2
（3）左上角的数字2+1=3,因为此时C1==C2
所以最终结果是3。
在填写过程中我们还是记录下当前单元格的数字来自于哪个单元格，以方便最后我们回溯找出最长公共子串。有时候左上、左、上三者中有多个同时达到最大，那么任取其中之一，但是在整个过程中你必须遵循固定的优先标准。在我的代码中优先级别是左上>左>上。
下图给出了回溯法找出LCS的过程：
奉上代码：
#include<iostream> #include<cstring> #include<stack> #include<utility> #define LEFTUP 0 #define LEFT 1 #define UP 2 using namespace std; int Max(int a,int b,int c,int *max){ //找最大者时a的优先级别最高，c的最低.最大值保存在*max中 int res=0; //res记录来自于哪个单元格 *max=a; if(b>*max){ *max=b; res=1; } if(c>*max){ *max=c; res=2; } return res; } //调用此函数时请注意把较长的字符串赋给str1,这主要是为了在回溯最长子序列时节省时间。如果没有把较长的字符串赋给str1不影响程序的正确执行。 string LCS(const string &str1,const string &str2){ int xlen=str1.size(); //横向长度 int ylen=str2.size(); //纵向长度 if(xlen==0||ylen==0) //str1和str2中只要有一个为空，则返回空 return ""; pair<int,int> arr[ylen+1][xlen+1]; //构造pair二维数组，first记录数据，second记录来源 for(int i=0;i<=xlen;i++) //首行清0 arr[0][i].first=0; for(int j=0;j<=ylen;j++) //首列清0 arr[j][0].first=0; for(int i=1;i<=ylen;i++){ char s=str2.at(i-1); for(int j=1;j<=xlen;j++){ int leftup=arr[i-1][j-1].first; int left=arr[i][j-1].first; int up=arr[i-1][j].first; if(str1.at(j-1)==s) //C1==C2 leftup++; int max; arr[i][j].second=Max(leftup,left,up,&arr[i][j].first); // cout<<arr[i][j].first<<arr[i][j].second<<" "; } // cout<<endl; } /*矩阵构造完毕*/ //回溯找出最长公共子序列 stack<int> st; int i=ylen,j=xlen; while(i>=0&&j>=0){ if(arr[i][j].second==LEFTUP){ if(arr[i][j].first==arr[i-1][j-1].first+1) st.push(i); --i; --j; } else if(arr[i][j].second==LEFT){ --j; } else if(arr[i][j].second==UP){ --i; } } string res=""; while(!st.empty()){ int index=st.top()-1; res.append(str2.substr(index,1)); st.pop(); } return res; } int main(){ string str1="GCCCTAGCG"; string str2="GCGCAATG"; string lcs=LCS(str1,str2); cout<<lcs<<endl; return 0; }
原文：http://www.cnblogs.com/topW2W/p/5092635.html