首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个
admin
2019-03-29
109
问题
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
例如:输入两个字符串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
程序员面试
相关试题推荐
求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。
判断单链表中是否存在环(网上说的笔试题)
UDP连接和TCP连接的异同。
输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。输出该树的深度3。二元树的结点定义如下:structSBinaryTreeNode//anodeofthe
整理收藏夹重新命名“新闻”子文件夹为“我的新闻”。
在IE中,请将Intetnet区域内站点的安全级别设置为“禁止ActiveX控件和插件运行”。
利用快捷菜单将桌面上的图标按“类型”排列。
加强网络道德建设,有利于加快信息安全立法的进程。
随着网络信息技术的进步和社会信息化程度的不断提高,一个由庞大的网络产业带动,并导致整个经济社会产生巨大变革的数字经济时代已经离我们越来越近。目前,“数字化校园”、“数字企业”、“数字城市”等一系列项目快速上马,在这些项目中,信息的数字化与数字信息的网络传输
随机试题
有关组织目标、任务、方针、政策的信息,自上而下地传达、贯彻的过程指的是
主张限制进口、奖励出口,以有利于本同牛产厂商发展的政策是
关于眼眶肿瘤下列哪项是错误的()
可吸入性粉尘的直径小于()
患者女,24岁。与同事发生口角后出现手舞足蹈,喊叫、打滚,一会又喊着对方的名字骂,约半小时左右恢复正常。患者以前也有类似发作3次,脑电图等检查均未发现异常。最可能的诊断是
同一长度的压杆,截面积及材料均相同,仅两端支承条件不同,则()杆的临界力最小。
Hisfirstbook______nextmonthisbasedonatruestory.
Dogsaresocialanimalsandwithoutpropertraining,theywillbehavelikewildanimals.Theywillspoilyourhouse,destroyyou
TheWestlifestoryreallybeganwaybackinDecember1996whenthethreeoriginalmembersofWestlifewereperforminginalocal
Increasingnumbersoffarmersaregrowinggeneticallyengineeredcrops.Anewreportalsosaysthatthetotallandareawheresu
最新回复
(
0
)