首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个
admin
2019-03-29
131
问题
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
例如:输入两个字符串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
程序员面试
相关试题推荐
Nowhereinnatureisaluminumfoundfree,owingtoitsalways______withotherelements,mostcommonlywithoxygen.
Studyingiseasierwhenone______thebigpubliclibraries.
Individualsandbusinesseshavelegalprotectionforintellectualpropertytheycreateandown.Intellectualproper【C1】______fro
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
输入一个表示整数的字符串,把该字符串转换成整数并输出。例如输入字符串"345",则输出整数345。
在用户管理组administrators中添加本地用户“sy”。
设置"考试"文件夹为"只读",并同时应用于所有子文件夹和文件。
请将"回收站"中名为"美丽城市.bmp"的文件删除。
在数据库系统中,“事务”是访问数据库并可能更新各种数据项的一个程序执行单元。为了保证数据完整性,要求数据库系统维护事务的原子性、一致性、隔离性和持久性。针对事务的这4种特性,考虑以下的架构设计场景:假设在某一个时刻只有一个活动的事务,为了保证事务
对计算机评价的主要性能指标有时钟频率、①、运算精度和内存容量等。对数据库管理系统评价的主要性能指标有②、数据库所允许的索引数量和最大并发事务处理能力等。①处应填入?
随机试题
Patrickwas______leaderofthebaseballteamofthecollege.
根据部位,下列哪种胃溃疡最为多见?
A.肌萎缩从上肢远端开始,逐渐发展到下肢,感觉无明显改变B.症状以肩部疼痛和活动障碍为主,可延续到上臂中部,痛点用局部封闭的方怯有较好的疗效C.症状以头晕,头痛为主,颈伸或侧弯眩晕明显,并可出现恶心,耳鸣和猝倒的症状D.症状为眩晕,耳鸣,恶心呕吐。发
使用开窍剂时应注意
脾的统血功能是靠气的哪种作用来实现的
广告忠告语为“请按药品说明书或在药师指导下购买和使用”的药品是
根据现行《宪法》规定,关于公民权利和自由,下列哪一选项是正确的?(卷一/2008年第17题)
与机械传动相比,液压传动的主要优点有()。
“平等、确实、便利、省费”的税收原则的提出者是()。
塞尔弗里奇提出了著名的“泛魔”识别模型,下列说法符合这一模式的有()
最新回复
(
0
)