先说两个的办法。如果只有两个字符串，可以先建一个二维数组（实际上用不到二维数组,下面再详细说），如input和reputation,如下：
i n p u t
r 0 0 0 0 0
e 0 0 0 0 0
p 0 0 1 0 0
u 0 0 0 2 0
t 0 0 0 0 3
a 0 0 0 0 0
t 0 0 0 0 1
i 1 0 0 0 0
o 0 0 0 0 0
n 0 1 0 0 0
其中的数字含义如下，0表示相应行和列的字符不相等，不是零就表示从这个字符开始，前n个字符是相同的，n就是那个数。比如第5列，第5行是3，表示input和reputation都有put这个子串。这些数里边有一个最大的，找出来就是了。
所以可以看出，对于两个字符串的问题，如果你不是想把所有的最长公共子串都找出来的话，可以逐行逐列地计算，只要在计算过程中保留最大值就可以了。
怎么"逐行逐列"地计算呢？可以先算第一行第一列，然后每一行每一列都通过上一行上一列算出。如果两个字符不相等，就为零。如果相等，就是左上角的数+1。因此算出了下一行和下一列，上一行和上一列就可以不要了。因为我们纵保存最大值，和产生最大值的位置。所谓动态规划，就是你算出下一行下一列，上一行上一列就可以不要了。
大家可以看出，如果有多个字符串，必须保留这个数组，因为如果不要这个数组，就无法保存所有的公共子串。为什么要保留所有的公共子串呢？因为两个字符串的最长公共子串不一定是所有字符串的最长公共子串，可能根本就不是公共子串。于是多个字符串的公共子串问题的思路就是这样：
1，先读入一个字符串。初始化公共子串表。
2，读入一个字符串，如果到了文件结尾，结束。
3，产生并保存公共子串表里所有的子串和当前字符串的公共子串，用这些新的公共子串组成新的公共子串表。
4，goto 2.
好像所有问题解决了。但是我的同学对我说：为了使每两个字符只比较一次，必须把粘连在一起的公共子串一起和新的当前字符串比较。什么是"粘连在一起的子串"呢？比如对于当前字符串inpaput,在字符串input中inp和put都是公共子串。如果我们把它们分开和下一个当前字符串比较，那么这两个公共子串的公共部分p就和新的当前子串的每一个字符比较了两次，如果我们将inp和put视为整体，那么p只需要和新当前子串的每一个字符比较一次。比如新子串是purple,图示如下：
i n p
p 0 0 1
u 0 0 0
r 0 0 0
p 0 0 1
l 0 0 0
e 0 0 0
p u t
p 1 0 0
u 0 2 0
r 0 0 0
p 1 0 0
l 0 0 0
e 0 0 0
比了两次
i n p u t
p 0 0 1 0 0
u 0 0 0 2 0
r 0 0 0 0 0
p 0 0 1 0 0
l 0 0 0 0 0
e 0 0 0 0 0
只比了一次。
可见，如果字符串类似于abcd和bcde,那么重复的工作就更多了。因此必须一起比较。这样编程的、复杂度会增加，但是效率会高一些。 |
|
收藏
淘帖
踩
