UC知道谁能帮我写下作业?或提供资源?附题目和解答思路
来源：百度知道 编辑：UC知道 时间：2024/05/29 20:21:24
求最长的公共子串(NOI'93第一题)
求N个字符串的最长公共子串，N<20，字符串长度不超过255。例如N=3，由键盘 依次输入3个字符串为
What is local bus ?
Name some local buses.
local bus is a high speed I/O bus close to the processor.
则最长公共子串为"local bus"。
此题也是作为第一题出现，同样有很多入在此题上失分。我们都做过求n个数最大公 约数的问题，在那道题中求3个数的最大公约数时，可以先求两个数的最大公约数，再将此数与第三个数求一次最大公约数。有人从那道题中得到"启发"，设s(p,q)为字符串p 和q的最长公共子串，则p、q、r的最长公共子串为s(s(p,q),r)。这样只需编写一个求两个字符串的最长公共子串的过程即可。但这种方法对不对呢?看看下面的例子。
三个字符串分别为'abc'、'cab'、'c'，则s(p,q)='ab',s(s(p,q).r)=''。事实上这三个字符串有公共子串'c'。显然上面的算法是错误的，原因在于没有考虑到本题与求最大公约数那道题在性质上的不同之处。最大公约数可以由局部解得到全局解，而本题却不能。正确的做法是列举出其中一个字符串的所有子串，找出其中最长的而且是公共的子串。
FOR i:=l TO 第一个字符串的长度 DO
FOR j:=i TO 第一个字符串的长度 DO
IF (第i个字符到第j个字符的子串为公共子串)AND(j-i+1>当前找到的最长公共子串的长度max)
THEN
BEGIN
max:=j-i+l;
最长公共子串:=此子串;
END;
为了提高效率，我们可以将最短的字符串作为第一个字符串。此题需要考虑的并不
求N个字符串的最长公共子串，N<20，字符串长度不超过255。例如N=3，由键盘 依次输入3个字符串为
What is local bus ?
Name some local buses.
local bus is a high speed I/O bus close to the processor.
则最长公共子串为"local bus"。
此题也是作为第一题出现，同样有很多入在此题上失分。我们都做过求n个数最大公 约数的问题，在那道题中求3个数的最大公约数时，可以先求两个数的最大公约数，再将此数与第三个数求一次最大公约数。有人从那道题中得到"启发"，设s(p,q)为字符串p 和q的最长公共子串，则p、q、r的最长公共子串为s(s(p,q),r)。这样只需编写一个求两个字符串的最长公共子串的过程即可。但这种方法对不对呢?看看下面的例子。
三个字符串分别为'abc'、'cab'、'c'，则s(p,q)='ab',s(s(p,q).r)=''。事实上这三个字符串有公共子串'c'。显然上面的算法是错误的，原因在于没有考虑到本题与求最大公约数那道题在性质上的不同之处。最大公约数可以由局部解得到全局解，而本题却不能。正确的做法是列举出其中一个字符串的所有子串，找出其中最长的而且是公共的子串。
FOR i:=l TO 第一个字符串的长度 DO
FOR j:=i TO 第一个字符串的长度 DO
IF (第i个字符到第j个字符的子串为公共子串)AND(j-i+1>当前找到的最长公共子串的长度max)
THEN
BEGIN
max:=j-i+l;
最长公共子串:=此子串;
END;
为了提高效率，我们可以将最短的字符串作为第一个字符串。此题需要考虑的并不
这个题有这么麻烦吗？我没想的太仔细，把最短字符串作为第一个参与对象就可以避免为'abc'、'cab'、'c'的问题了吧？
把最短字符串作为第一个参与对象就可以避免为'abc'、'cab'、'c'的问题了，我告你吧，加我！