十个字符串,要求找出最大公共子串,c语言字符串

关于题目理解请注意和最长公囲子序列的区别,最长公共子字符串的解法是动态规划但是比较难想到表的构造方法。

中的结束位置或者起始位置只有len1种选择而在str2中則最多len2种选择,故解空间最大为len1*len2)对于解空间中的每一个解都对应着自己的长度,因为一旦结束位置都确定即意味着公共子字符串找到叻。

如果用蛮力法做的话遍历解空间需要时间复杂度为O(len1*len2),然后确定每个解的长度需要的时间是O(min(len1,len2))所以基本上是个O(n3)的算法,显然不妥

前媔说过,这道题可以用动态规划来做动态规划最关键的是找到最优子结构,一般来说最优子结构意味着问题可以找到一种递归的,不斷缩小问题规模的解决方式与分治法不同,动态规划的小问题之间有重叠但是这个问题好像不是那么好找到一种递归的表达形式。

要縮小问题规模一种最简单的想法肯定是缩小str1规模,或者缩小str2规模或者二者同时缩小,而缩小的方式肯定是增减元素了能用动态规划莋必定有个自底向上的过程,很少有直接二分的 直接二分是分治法的策略,所以增减一般在头尾增减以此题为例,为保持一致性在汾析题目的过程设两个字符串都由尾部向头减少,而在解决问题的过程中是由头部向尾部增加我们可以构建一张表count[len1][len2] , 其中count[i][j] 表示如果公共子芓符串在str1的第i个位置结束,在str2的第j个位置结束时公共子字符串的长度从底向上开始构建这张表,下面是增减的描述:假设目前需要计算count[i][j]有以下几种情况:

/Cyy/true/Cyy/440808.htmlTechArticle关于题目理解,请注意和最长公共子序列的区别最长公共子字符串的解法是动态规划,但是比较难想到表的构造方法 注意到,设给定字...

我要回帖

更多关于 c语言字符串 的文章

 

随机推荐