2：求串S，T，L的公共子串
不一定要知道具体算法（有当然更好：）），只求思想！
谢谢
9 个解决方案
#1
我有一个笨办法，比如“abcdef”，“wefcdewga”，就把长度小的串的子串由大到小取出来，如果其他串里包含这个子串，那么就找到一个公共子串，3个4个或更多的串求公共子串与之类似。
不知有没有好点的方法
不知有没有好点的方法
#2
最笨蛋的方法就是逐个比较.类似穷举!:(
#3
数据结构书上有!三各算法
1.简介的样品匹配算法
2.KMP样品匹配算法
3.BM(boyer-Moore)算法
1.简介的样品匹配算法
2.KMP样品匹配算法
3.BM(boyer-Moore)算法
#4
up
#5
up
#6
up
看看《数据结构》书
看看《数据结构》书
#7
1先求出最长公共子串.
假设两个串的串长分别为m和n，且不失一般性可以假设m>=n。则此问题的算法为从长度为n的串中取第i(i=0,1,…,n-len)个字符起长度为len(len=n,n-1,…,1)的子串和长度为m的串相匹配，从中找出长度最大的子串。
假设两个串的串长分别为m和n，且不失一般性可以假设m>=n。则此问题的算法为从长度为n的串中取第i(i=0,1,…,n-len)个字符起长度为len(len=n,n-1,…,1)的子串和长度为m的串相匹配，从中找出长度最大的子串。
#8
用眼睛看
#9
2也是先求出最长公共子串.
采用的是广义后缀树（Generalized Suffix Tree，简称GST)算法，就是把给定的N个源字符串的所有的后缀建成一颗树，这个树有以下一些特点：
1.树的每个节点是一个字符串，树根是空字符串“”
2.任意一个后缀子串都可以由一条从根开始的路径表达 将这条路径上的节点字符串依次拼接起来就可以得到这个后缀）
3.特别应注意任意一个子串都可以看作某一个后缀的前缀。既然每一个后缀 都可以由一条从根开始的路径表达，那么我们可以从根节点开始一个字符 一个字符的跟踪这条路径从而得到任意一个子串。
4.为了满足查找公共子串的需求，每个节点还应该有从属于哪个源字符串的信息
由以上的定义我们不难看出，在这棵GST树上，如果找到深度最大并且从属于所有源字串的节点，那么，把从根到这个节点的路径上的所有节点字符串拼接起来就是LCS。
采用的是广义后缀树（Generalized Suffix Tree，简称GST)算法，就是把给定的N个源字符串的所有的后缀建成一颗树，这个树有以下一些特点：
1.树的每个节点是一个字符串，树根是空字符串“”
2.任意一个后缀子串都可以由一条从根开始的路径表达 将这条路径上的节点字符串依次拼接起来就可以得到这个后缀）
3.特别应注意任意一个子串都可以看作某一个后缀的前缀。既然每一个后缀 都可以由一条从根开始的路径表达，那么我们可以从根节点开始一个字符 一个字符的跟踪这条路径从而得到任意一个子串。
4.为了满足查找公共子串的需求，每个节点还应该有从属于哪个源字符串的信息
由以上的定义我们不难看出，在这棵GST树上，如果找到深度最大并且从属于所有源字串的节点，那么，把从根到这个节点的路径上的所有节点字符串拼接起来就是LCS。
#1
我有一个笨办法，比如“abcdef”，“wefcdewga”，就把长度小的串的子串由大到小取出来，如果其他串里包含这个子串，那么就找到一个公共子串，3个4个或更多的串求公共子串与之类似。
不知有没有好点的方法
不知有没有好点的方法
#2
最笨蛋的方法就是逐个比较.类似穷举!:(
#3
数据结构书上有!三各算法
1.简介的样品匹配算法
2.KMP样品匹配算法
3.BM(boyer-Moore)算法
1.简介的样品匹配算法
2.KMP样品匹配算法
3.BM(boyer-Moore)算法
#4
up
#5
up
#6
up
看看《数据结构》书
看看《数据结构》书
#7
1先求出最长公共子串.
假设两个串的串长分别为m和n，且不失一般性可以假设m>=n。则此问题的算法为从长度为n的串中取第i(i=0,1,…,n-len)个字符起长度为len(len=n,n-1,…,1)的子串和长度为m的串相匹配，从中找出长度最大的子串。
假设两个串的串长分别为m和n，且不失一般性可以假设m>=n。则此问题的算法为从长度为n的串中取第i(i=0,1,…,n-len)个字符起长度为len(len=n,n-1,…,1)的子串和长度为m的串相匹配，从中找出长度最大的子串。
#8
用眼睛看
#9
2也是先求出最长公共子串.
采用的是广义后缀树（Generalized Suffix Tree，简称GST)算法，就是把给定的N个源字符串的所有的后缀建成一颗树，这个树有以下一些特点：
1.树的每个节点是一个字符串，树根是空字符串“”
2.任意一个后缀子串都可以由一条从根开始的路径表达 将这条路径上的节点字符串依次拼接起来就可以得到这个后缀）
3.特别应注意任意一个子串都可以看作某一个后缀的前缀。既然每一个后缀 都可以由一条从根开始的路径表达，那么我们可以从根节点开始一个字符 一个字符的跟踪这条路径从而得到任意一个子串。
4.为了满足查找公共子串的需求，每个节点还应该有从属于哪个源字符串的信息
由以上的定义我们不难看出，在这棵GST树上，如果找到深度最大并且从属于所有源字串的节点，那么，把从根到这个节点的路径上的所有节点字符串拼接起来就是LCS。
采用的是广义后缀树（Generalized Suffix Tree，简称GST)算法，就是把给定的N个源字符串的所有的后缀建成一颗树，这个树有以下一些特点：
1.树的每个节点是一个字符串，树根是空字符串“”
2.任意一个后缀子串都可以由一条从根开始的路径表达 将这条路径上的节点字符串依次拼接起来就可以得到这个后缀）
3.特别应注意任意一个子串都可以看作某一个后缀的前缀。既然每一个后缀 都可以由一条从根开始的路径表达，那么我们可以从根节点开始一个字符 一个字符的跟踪这条路径从而得到任意一个子串。
4.为了满足查找公共子串的需求，每个节点还应该有从属于哪个源字符串的信息
由以上的定义我们不难看出，在这棵GST树上，如果找到深度最大并且从属于所有源字串的节点，那么，把从根到这个节点的路径上的所有节点字符串拼接起来就是LCS。