16762人阅读
数据结构（60）
C/C++（62）
&&&&&& 题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子序列，并打印出最长公共子序列。
&&&&& 例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子序列，则输出它们的长度4，并打印任意一个子序列。
&&&&&& 分析：求最长公共子序列（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，因此一些重视算法的公司像MicroStrategy都把它当作面试题。
&&&&& &完整介绍动态规划将需要很长的篇幅，因此我不打算在此全面讨论动态规划相关的概念，只集中对LCS直接相关内容作讨论。如果对动态规划不是很熟悉，请参考相关算法书比如算法讨论。
&&&&&& 考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：
（1） 如果am-1==bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；
（2） 如果am-1!=bn-1，则若zk-1!=am-1时，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；
（3） 如果am-1!=bn-1，则若zk-1!=bn-1时，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。
&&&&& 这样，在找A和B的公共子序列时，如果有am-1==bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。
&&&&&&&求解：
&&&&&& 引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定输出最长公共字串时搜索的方向。
&&&&& 我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] == Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。
&&&&& 问题的递归式写成：
&&&&& 回溯输出最长公共子序列过程：
&&&&&& 算法分析：
&&&&& 由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m + n)。
&&&&& 完整的实现代码如下：
找出两个字符串的最长公共子序列的长度
** author :liuzhiwei
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
int LCSLength(char* str1, char* str2, int **b)
int i,j,length1,length2,
length1 = strlen(str1);
length2 = strlen(str2);
//双指针的方法申请动态二维数组
int **c = new int*[length1+1];
//共有length1+1行
for(i = 0; i & length1+1; i++)
c[i] = new int[length2+1];
//共有length2+1列
for(i = 0; i & length1+1; i++)
c[i][0]=0;
//第0列都初始化为0
for(j = 0; j & length2+1; j++)
c[0][j]=0;
//第0行都初始化为0
for(i = 1; i & length1+1; i++)
for(j = 1; j & length2+1; j++)
if(str1[i-1]==str2[j-1])
//由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-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;
c[i][j]=c[i][j-1];
b[i][j]=-1;
for(i= 0; i & length1+1; i++)
for(j = 0; j & length2+1; j++)
printf(&%d &,c[i][j]);
printf(&\n&);
len=c[length1][length2];
for(i = 0; i & length1+1; i++)
//释放动态申请的二维数组
delete[] c[i];
void PrintLCS(int **b, char *str1, int i, int j)
if(i==0 || j==0)
if(b[i][j]==0)
PrintLCS(b, str1, i-1, j-1);
//从后面开始递归，所以要先递归到子串的前面，然后从前往后开始输出子串
printf(&%c&,str1[i-1]);
//c[][]的第i行元素对应str1的第i-1个元素
else if(b[i][j]==1)
PrintLCS(b, str1, i-1, j);
PrintLCS(b, str1, i, j-1);
int main(void)
char str1[100],str2[100];
int i,length1,length2,
printf(&请输入第一个字符串：&);
gets(str1);
printf(&请输入第二个字符串：&);
gets(str2);
length1 = strlen(str1);
length2 = strlen(str2);
//双指针的方法申请动态二维数组
int **b = new int*[length1+1];
for(i= 0; i & length1+1; i++)
b[i] = new int[length2+1];
len=LCSLength(str1,str2,b);
printf(&最长公共子序列的长度为：%d\n&,len);
printf(&最长公共子序列为：&);
PrintLCS(b,str1,length1,length2);
printf(&\n&);
for(i = 0; i & length1+1; i++)
//释放动态申请的二维数组
delete[] b[i];
system(&pause&);
&&&&&&&&& 程序的效果图如下：
&&&&& 第二种方法为：
找出两个字符串的最长公共子序列的长度
** author :liuzhiwei
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
int LCSLength(char* str1, char* str2)
//求得两个字符串的最大公共子串长度并输出公共子串
int i,j,length1,length2;
length1 = strlen(str1);
length2 = strlen(str2);
//双指针的方法申请动态二维数组
int **c = new int*[length1+1];
//共有length1+1行
for(i = 0; i & length1+1; i++)
c[i] = new int[length2+1];
//共有length2+1列
for(i = 0; i & length1+1; i++)
c[i][0]=0;
//第0列都初始化为0
for(j = 0; j & length2+1; j++)
c[0][j]=0;
//第0行都初始化为0
for(i = 1; i & length1+1; i++)
for(j = 1; j & length2+1; j++)
if(str1[i-1]==str2[j-1])
//由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-1个元素
c[i][j]=c[i-1][j-1]+1;
else if(c[i-1][j]&c[i][j-1])
c[i][j]=c[i-1][j];
c[i][j]=c[i][j-1];
//输出公共子串
char s[100];
int len,k;
len=k=c[length1][length2];
s[k--]='\0';
i=length1,j=length2;
while(i&0 && j&0)
if(str1[i-1]==str2[j-1])
s[k--]=str1[i-1];
else if(c[i-1][j]&c[i][j-1])
printf(&最长公共子串为：&);
for(i = 0; i & length1+1; i++)
//释放动态申请的二维数组
delete[] c[i];
int main(void)
char str1[100],str2[100];
int length1,length2,
printf(&请输入第一个字符串：&);
gets(str1);
printf(&请输入第二个字符串：&);
gets(str2);
length1 = strlen(str1);
length2 = strlen(str2);
len=LCSLength(str1,str2);
printf(&最长公共子串的长度为：%d\n&,len);
system(&pause&);
&&&&&& 问题拓展：设A、B、C是三个长为n的字符串，它们取自同一常数大小的字母表。设计一个找出三个串的最长公共子序列的O(n^3)的时间算法。
&&&&&& 思路：跟上面的求2个字符串的公共子序列是一样的思路，只不过这里需要动态申请一个三维的数组，三个字符串的尾字符不同的时候，考虑的情况多一些而已。
找出三个字符串的最长公共子序列的长度
** author :liuzhiwei
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
int max1(int m,int n)
int max2(int x,int y,int z,int k,int m,int n)
int max=-1;
int LCSLength(char* str1, char* str2, char* str3)
//求得三个字符串的最大公共子序列长度并输出公共子序列
int i,j,k,length1,length2,length3,
length1 = strlen(str1);
length2 = strlen(str2);
length3 = strlen(str3);
//申请动态三维数组
int ***c = new int**[length1+1];
//共有length1+1行
for(i = 0; i & length1+1; i++)
c[i] = new int*[length2+1];
//共有length2+1列
for(j = 0; j&length2+1; j++)
c[i][j] = new int[length3+1];
for(i = 0; i & length1+1; i++)
for(j = 0; j & length2+1; j++)
c[i][j][0]=0;
for(i = 0; i & length2+1; i++)
for(j = 0; j & length3+1; j++)
c[0][i][j]=0;
for(i = 0; i & length1+1; i++)
for(j = 0; j & length3+1; j++)
c[i][0][j]=0;
for(i = 1; i & length1+1; i++)
for(j = 1; j & length2+1; j++)
for(k = 1; k & length3+1; k++)
if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1])
c[i][j][k]=c[i-1][j-1][k-1]+1;
else if(str1[i-1]==str2[j-1] && str1[i-1]!=str3[k-1])
c[i][j][k]=max1(c[i][j][k-1],c[i-1][j-1][k]);
else if(str1[i-1]==str3[k-1] && str1[i-1]!=str2[j-1])
c[i][j][k]=max1(c[i][j-1][k],c[i-1][j][k-1]);
else if(str2[j-1]==str3[k-1] && str1[i-1]!=str2[j-1])
c[i][j][k]=max1(c[i-1][j][k],c[i][j-1][k-1]);
c[i][j][k]=max2(c[i-1][j][k],c[i][j-1][k],c[i][j][k-1],c[i-1][j-1][k],c[i-1][j][k-1],c[i][j-1][k-1]);
len=c[length1][length2][length3];
for(i = 1; i & length1+1; i++)
//释放动态申请的三维数组
for(j = 1; j & length2+1; j++)
delete[] c[i][j];
delete[] c[i];
int main(void)
char str1[100],str2[100],str3[100];
printf(&请输入第一个字符串：&);
gets(str1);
printf(&请输入第二个字符串：&);
gets(str2);
printf(&请输入第三个字符串：&);
gets(str3);
len=LCSLength(str1,str2,str3);
printf(&最长公共子序列的长度为：%d\n&,len);
system(&pause&);
&&&&&&& 程序的效果图如下：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3366394次
积分：31019
积分：31019
排名：第119名
原创：254篇
评论：2554条
文章：14篇
阅读：32316
文章：18篇
阅读：500194
(1)(9)(1)(2)(4)(2)(2)(9)(2)(9)(10)(19)(20)(16)(18)(2)(2)(19)(10)(61)(14)(30)题目大意：
给出两个长度小于等于25W的字符串，求它们的最长公共子串。
题目链接：
算法讨论：
二分+哈希， 后缀数组， 后缀自动机。
随意做。这里面只写一下我对后缀自动机做法的理解。
首先，我们假设两个串分别为A串和B串，我们先对建立出A串的后缀自动机，然后对于B串的每一位，我们进行如下的操作：首先从第1位开始，Parent树上的位置在root，那么对于每一次操作，如果当前结点的字符可以匹配当前B串中所考虑到的字符，那么自然就len ++,然后继续沿着Parent树向下走。如果当前失配，那么根据&在Parent树上某一个结点状态的pre指针指向的是可以接收同样后缀的状态结点&这条性质，我们在parent树上向上跳。此时，根据parent树原理，其父亲的right集合元素数目变多，字符串长度变短，那么，就可以这么考虑，刚刚在s(临时设个变量表示长度)长度的时候不能完全匹配，所以我们只有减小长度才有再次匹配成功的可能，所以要凭借Parent树来完成（因为Father的Right集合元素数多，所以字符串长度就短），我们沿着Parent树向上跳，这时会出现两种情况，第一，跳到了-1.也就是null状态，这说明B[i]（假设当前正在考虑第i个子串）没有在A串中出现，所以此时把len清0，然后Parent树上位置回root，从新考虑。第二，找到了匹配位置，那么len = st[p].len + 1, p为当前在Parent树上的位置，为什么这样呢？考虑b[i]可以在p这个状态结点成功匹配，由于我们是从Parent上找到这个结点的，所以其前面的字符一定都是匹配的。举个例子，假设我们当前已经成功匹配了2个字符（不是定是B串中的前两个字符，因为是子串），现在考虑b[i],即可能成为成功匹配的第三个字符，如果在p成功匹配，那么由于在Parent树上向上跳了，因为上面提到的性质（Parent树的父亲的状态表示的子串是其儿子的最长后缀），子串长度会变短。假设变短1，所以匹配完后长度变成了2.。。。
1 #include &bits/stdc++.h&
2 using namespace
3 const int L = 250000 + 5;
5 struct State{
int next[26];
8 }st[L&&1];
10 struct SuffixAutomaton{
void Init(){
st[0].len = 0; st[0].fa = -1;
void Extend(int c){
int cur = sz ++;
st[cur].len = st[last].len + 1;
for(p = p != -1 && !st[p].next[c]; p = st[p].fa)
st[p].next[c] =
if(p == -1) st[cur].fa = 0;
int q = st[p].next[c];
if(st[q].len == st[p].len + 1) st[cur].fa =
int cle = sz ++;
st[cle].len = st[p].len + 1;
st[cle].fa = st[q].
for(int i = 0; i & 26; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != -1 && st[p].next[c] == p = st[p].fa)
st[p].next[c] =
st[q].fa = st[cur].fa =
44 char str1[L], str2[L];
46 int main(){
scanf("%s%s", str1, str2);
int len1 = strlen(str1), len2 = strlen(str2);
int ans = 0;
SAM.Init();
for(int i = 0; i & len1; ++ i)
SAM.Extend(str1[i] - 'a');
int p = 0, len = 0;
for(int i = 0; i & len2; ++ i){
int x = str2[i] - 'a';
if(st[p].next[x]){
p = st[p].next[x];
while(p != -1 && !st[p].next[x]) p = st[p].
if(p == -1){
len = 0; p = 0;
len = st[p].len + 1; p = st[p].next[x];
ans = max(ans, len);
printf("%d\n", ans);
阅读(...) 评论()