首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个
admin
2019-03-29
56
问题
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
例如:输入两个字符串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://jikaoti.com/ti/Mag7FFFM
0
程序员面试
相关试题推荐
[A]Theperson-skillsmatchapproachtoselection[B]Theimpactsofbadselectiondecisions[C]Theimportanceofstructu
公司要求开发一个继承System.Windows.Forms.ListView类的组件,要求达到以下的特殊功能:点击ListView各列列头时,能按照点击列的每行值进行重排视图中的所有行(排序的方式如DataGrid相似)。根据您的知识,请简要谈一下您的
活动目录的作用
通过网上邻居查找名字为mary的计算机。
设置用户在拨号前不需要等待扬声器发出拨号声音。
从当前界面上的菜单或“网络任务”开始创建拨号连接,通过Modem连接到In-ternet,拨号时先拨0,再拨16300,用户名和密码均为16300,将创建的连接的名称命名为:linkl,然后在桌面上创建一个到此连接的快捷方式。除此之外,其余选项均使用默认设
计算机通信的两个最主要的指标是()A.数据传输速率和误码率B.衰减和失效率C.高效率和正确率D.硬件利用率和软件利用率
关于PPoint97启动对话框的描述,()是错误的。A.使用“内容提示向导”,能在系统提示下创建新演示文稿B.使用“模板”可生成具有一定布局和色彩的幻灯片C.“打开已有的演示文稿”选项没有任何作用D.使用“空演示文稿”创建一张空白幻灯片
简述企业应用集成的内容层次,并比较EAI与ERP,CMM的异同。简述在你开发企业级应用集成平台后运行的具体效果。现在你认为还有哪些可改进之处以及如何去改进?
简述企业应用集成的内容层次,并比较EAI与ERP,CMM的异同。具体叙述实施企业应用集成的要点,详细论述你在选择企业级应用集成(EAI)解决方案时的考虑,采用技术与方法。
随机试题
肠瘘是引起下列哪项酸碱平衡紊乱的原因
乌梅丸的组方特点中不包括
季先生,因十二指肠溃疡并发瘢痕性幽门梗阻,反复呕吐宿食,消瘦,皮肤干燥,弹性消失入院后经充分术前准备,在硬脊膜外麻醉下行胃大部切除术。术前护理中哪一项是特殊准备()。
如果非公开发行且有明确锁定期的股票取得成本,低于交易所交易的同一股票的市价,则应该用()作为该股票的价值。
为防止经营者背离股东目标,股东可以采取的措施不包括()。
M注册会计师完成了对A体育用品公司2005年度的会计报表的审计,并于2006年4月10日出具了审计报告,A公司的会计报表于4月15日公布。下列问题,请代为作出处理意见。
关于浮动薪酬说法正确的是()
教师违法(侵权)行为的主要类型有哪些?
党的十八大发出了向“两个一百年”奋斗目标进军的时代号召,“两个一百年”目标是()。
近年来,随着互联网的日益______,网络媒体已成为发布公共信息的重要平台,网民通过互联网______的社情民意也成为各级党政机关的重要决策依据。填入划横线部分最恰当的一项是()。
最新回复
(
0
)