首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个
admin
2019-03-29
42
问题
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串。
选项
答案
#include "string.h" // directions of LCS generation enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp}; ///////////////////////////////////////////////////////////////////////////// // Get the length of two strings’ LCSs, and print one of the LCSs // Input: pStr1 - the first string // pStr2 - the second string // Output: the length of two strings’ LCSs ///////////////////////////////////////////////////////////////////////////// int LCS(char* pStr1, char* pStr2) { if(!pStr1 || !pStr2) return 0; size_t length1 = strlen(pStr1); size_t length2 = strlen(pStr2); if(!length1 || !length2) return 0; size_t i, j; // initiate the length matrix int **LCS_length; LCS_length = (int**)(new int[length1]); for(i = 0; i < length1; ++ i) LCS_length[i] = (int*)new int[length2]; for(i = 0; i < length1; ++ i) for(j = 0; j < length2; ++ j) LCS_length[i][j] = 0; // initiate the direction matrix int **LCS_direction; LCS_direction = (int**)(new int[length1]); for( i = 0; i < length1; ++ i) LCS_direction[i] = (int*)new int[length2]; for(i = 0; i < length1; ++ i) for(j = 0; j < length2; ++ j) LCS_direction[i][j] = kInit; for(i = 0; i < length1; ++ i) { for(j = 0; j < length2; ++ j) { if(i == 0 || j == 0) { if(pStr1[i] == pStr2[j]) { LCS_length[i][j] = 1; LCS_direction[i][j] = kLeftUp; } else LCS_length[i][j] = 0; } // a char of LCS is found, // it comes from the left up entry in the direction matrix else if(pStr1[i] == pStr2[j]) { LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1; LCS_direction[i][j] = kLeftUp; } // it comes from the up entry in the direction matrix else if(LCS_length[i - 1][j] > LCS_length[i][j - 1]) { LCS_length[i][j] = LCS_length[i - 1][j]; LCS_direction[i][j] = kUp; } // it comes from the left entry in the direction matrix else { LCS_length[i][j] = LCS_length[i][j - 1]; LCS_direction[i][j] = kLeft; } } } LCS_Print(LCS_direction, pStr1, pStr2, length1 - 1, length2 - 1); return LCS_length[length1 - 1][length2 - 1]; } ///////////////////////////////////////////////////////////////////////////// // Print a LCS for two strings // Input: LCS_direction - a 2d matrix which records the direction of // LCS generation // pStr1 - the first string // pStr2 - the second string // row - the row index in the matrix LCS_direction // col - the column index in the matrix LCS_direction ///////////////////////////////////////////////////////////////////////////// void LCS_Print(int **LCS_direction, char* pStr1, char* pStr2, size_t row, size_t col) { if(pStr1 == NULL || pStr2 == NULL) return; size_t length1 = strlen(pStr1); size_t length2 = strlen(pStr2); if(length1 == 0 || length2 == 0 || !(row < length1 && col < length2)) return; // kLeftUp implies a char in the LCS is found if(LCS_direction[row][col] == kLeftUp) { if(row > 0 && col > 0) LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col - 1); // print the char printf("%c", pStr1[row]); } else if(LCS_direction[row][col] == kLeft) { // move to the left entry in the direction matrix if(col > 0) LCS_Print(LCS_direction, pStr1, pStr2, row, col - 1); } else if(LCS_direction[row][col] == kUp) { // move to the up entry in the direction matrix if(row > 0) LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col); } }
解析
求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。
完整介绍动态规划将需要很长的篇幅,因此我不打算在此全面讨论动态规划相关的概念,只集中对LCS直接相关内容作讨论。如果对动态规划不是很熟悉,请参考相关算法书比如算法讨论。
先介绍LCS问题的性质:记X
m
={x
0
, x
1
,…x
m-1
}和Y
n
={ y
0
, y
1
,…y
n-1
}为两个字符串,而Z
k
={ z
0
, z
1
,…z
k-1
}是它们的LCS,则:
1. 如果x
m-1
=y
n-1
,那么z
k-1
=x
m-1
=y
n-1
,并且Z
k-1
是X
m-1
和Y
n-1
的LCS;
2. 如果x
m-1
≠y
n-1
,那么当z
k-1
≠x
m-1
时Z是X
m-1
和Y的LCS;
3. 如果x
m-1
≠y
n-1
,那么当z
k-1
≠y
n-1
时Z是Y
n-1
和X的LCS;
下面简单证明一下这些性质:
1. 如果z
k-1
≠x
m-1
,那么我们可以把x
n-1
(y
k-1
)加到Z中得到Z’,这样就得到X和Y的一个长度为k+1的公共子串Z’。这就与长度为k的Z是X和Y的LCS相矛盾了。因此一定有z
k-1
=x
m-1
=y
n-1
。
既然z
k-1
=x
m-1
=y
n-1
,那如果我们删除z
k-1
(x
m-1
、y
n-1
)得到的Z
k-1
,X
m-1
和Y
n-1
,显然Z
k-1
是X
m-1
和Y
n-1
的一个公共子串,现在我们证明Z
k-1
是X
m-1
和Y
n-1
的LCS。用反证法不难证明。假设有X
m-1
和Y
n-1
有一个长度超过k-1的公共子串W,那么我们把加到W中得到W’,那W’就是X和Y的公共子串,并且长度超过k,这就和已知条件相矛盾了。
2.还是用反证法证明。假设Z不是X
m-1
和Y的LCS,则存在一个长度超过k的W是X
m-1
和Y的LCS,那W肯定也X和Y的公共子串,而已知条件中X和Y的公共子串的最大长度为k。矛盾。
3. 证明同2。
有了上面的性质,我们可以得出如下的思路:求两字符串X
m
={ x
0
, x
1
,…x
m-1
}和Y
n
={ y
0
, y
1
,…y
n-1
}的LCS,如果x
m-1
=yn-1,那么只需求得X
m-1
和Y
n-1
的LCS,并在其后添加x
m-1
(y
n-1
)即可;如果x
m-1
≠y
n-1
,我们分别求得X
m-1
和Y的LCS和Y
n-1
和X的LCS,并且这两个LCS中较长的一个为X和Y的LCS。
如果我们记字符串X
i
和Y
j
的LCS的长度为c[i,j],我们可以递归地求c[i,j]:
上面的公式用递归函数不难求得。但从前面求Fibonacci第n项的分析中我们知道直接递归会有很多重复计算,我们用从底向上循环求解的思路效率更高。
为了能够采用循环求解的思路,我们用一个矩阵(参考代码中的LCS_length)保存下来当前已经计算好了的c[i,j],当后面的计算需要这些数据时就可以直接从矩阵读取。另外,求取c[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到,相当于在矩阵LCS_length中是从c[i-1,j-1],c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j],因此在矩阵中有三种不同的移动方向:向左、向上和向左上方,其中只有向左上方移动时才表明找到LCS中的一个字符。于是我们需要用另外一个矩阵(参考代码中的LCS_direction)保存移动的方向。
转载请注明原文地址:https://kaotiyun.com/show/KxmZ777K
0
程序员面试
相关试题推荐
Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressyourownopinion.
大概描述一下ASP。NET页面的生命周期
不开辟新空间完成字符串的逆序
输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。输出该树的深度3。二元树的结点定义如下:structSBinaryTreeNode//anodeofthe
利用"开始"菜单的"运行"选项,启动"计算器"应用程序,计算器应用程序的标识为:c:\windows\system32\calc.exe(在"打开"中直接填写标识名)。
下列关于针式打印机的特点正确的有()。A.可以多层复写打印B.造价低廉C.工作噪音小D.打印速度高
windows应用程序窗口中的某一菜单中的某条命令被选中后,则出现一对话框,则该命令有()特点。A.后跟“…”B.前有“√”C.呈灰色D.后跟三角形符号
Dreamweaver的编辑(Edit)菜单命令中,SelectAll表示______。A.将剪贴板拷贝至当前光标位置B.从文档中删除当前选区C.选取当前文档中所有元素D.使用HTML代码将当前选区拷贝到剪贴板
()是计算机与网络的接口,计算机通过它向其他计算机发送信息,鉴别和接收其他计算机发送来的信息。
随机试题
处理工艺中低合金工具钢的含碳量与碳素工具钢含碳量相近,因此它们的淬火加热温度也很接近。
A.促进钙离子释出B.抑制镁离子释出C.抑制骨吸收D.吸收镁离子E.抑制磷的回吸收甲状旁腺激素对肾的主要作用是
A.链霉素B.异烟肼C.利福平D.乙胺丁醇E.左氧氟沙星下列副作用分别由哪种药物引起听力障碍
某公司2011年度利润总额为1350万元,财务费用为400万元,净利润为880万元,管理费用为800万元,该公司的利息保障倍数为()。
卫生局的做法是否正确。如果不正确,如何更正?如果卫生防疫站经过调查,正式对严某做出不颁发卫生许可证的决定,严某不服,想提起诉讼,该以谁为被告?理由何在?
关于施工现场环境噪声污染防治的说法,正确的是()。
废品损失采用按废品所耗定额费用计算不可修复废品成本时,废品的生产成本是按废品数量和各项费用定额计算的,不需要考虑废品实际发生的生产费用。()
下列选项中关于个案工作说法错误的是()。
A、 B、 C、 D、 C
Doctorsalreadyknowthatpeoplewhosmokecandamagetheirhearing.ThelateststudyinthejournalTobaccoControl,【C1】______m
最新回复
(
0
)