LCS最长公共子串算法
Sep 26th,2011
发表评论
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置.
下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232
声明: 本文采用 BY-NC-SA 协议进行授权. 转载请注明转自: LCS最长公共子串算法
评论 (0)
Trackbacks (0)
发表评论
Make a trackback