首页 > 代码库 > 最长公共子串问题(方法一:暴力+RK匹配,方法二:DP+空间优化)
最长公共子串问题(方法一:暴力+RK匹配,方法二:DP+空间优化)
时间:2014.09.05
地点:基地二楼
一、题目
给定一个query和一个text,均由小写字母组成。要求在text中找出以同样的顺序连续出现在query中的最长连续字母序列的长度。例如, query为“acbac”,text为“acaccbabb”,那么text中的“cba”为最长的连续出现在query中的字母序列,因此,返回结果应该为其长度3。
二、分析
对于该问题最直接的想法就是对query字符串的所有非空子字符串再text中进行查找比对,看是否也被包含在text中,然后取最长的那个的长度,即为所求。假设query字符串长度为n,那么query的子字符串就有C(n,2)个,即n(n-1)/2,然后这些子字符串还要在text中进行搜索匹配,朴素的搜索匹配算法复杂度是O(n^2),如此一来,该算法的时间复杂度为O(n^4),当然可以做一些优化,提高算法效率,比如对于匹配算法也还可以进行优化,比如RK算法,有限自动机和KMP算法等。
下面给出结合RK匹配的一个暴力算法代码:
1.先是RK算法,有关RK算法的再往后写出
bool RabinKarpMatch(const string& T, const string& P) { static const int d = 128; static const int q = 6999997; int n = T.length(); int m = P.length(); int h = 1; for (int i = 1; i < m; i++) h = (h*d) % q; //h=d^(m-1) mode q int p = 0, t = 0; for (int i = 0; i < m; ++i) //processing { p = ((p*d) + P[i]) % q; t = ((t*d) + T[i]) % q; } for (int s = 0; s < n - m + 1; ++s) //s=[0...n-m+1-1] { if (t== p) { int i = 0; for (i; i < m; ++i) { if (P[i] != T[s + i]) break; } if (i == m) return true; } t = (d*(t - T[s] * h% q+q) + T[s + m]) % q; } return false; }
2.然后是顶层实现
size_t GetLargestCommomSubLen(const string& text, const string& query) { size_t query_len = query.length(); size_t text_len = text.length(); assert(text_len >= query_len); if (text.empty() || query.empty()) return 0; size_t max_len = 0; for (size_t start = 0; start < query_len; ++start) { size_t size = query_len - start; for (size_t len = 1; len <= size; ++len) { if (RabinKarpMatch(text, query.substr(start, len))) { if (len>max_len) max_len = len; } } } return max_len; }
三、动态规划
记得有个斐波拉契数列问题,巧妙的用到了DP,使得算法效率得到了极大的改善,依照那种思路,先找到一种数学关系,类似F(n)=F(n-1)+F(n-2)或C(n,k)=C(n-1,k)+C(n-1,k-1),然后自底向上地去处理得到结果。在最长公共子字符串中这个问题表现为:
设text[ i ]和query[ j ]分别为上次匹配结尾的字符,在斐波拉契数列中,即是充分利用子问题的解去构造复杂问题的解,这里也一样,可用L[ i,j ]记录它们当前的匹配长度,于是在计算L[i+1,j+1]时,即匹配下一个字符时,只要看text[i+1]和query[j+1]还继不继续相等,相等则L[ i,j ]=L[ i-1,j-1 ] + 1,不相等则为0,结束匹配。再回到斐波拉契数列问题,在那里,用到自底向上的求解方式,首先是已知底为F(0)=0和F(1)=1,在这里,虽然不能很明显的知道底,然可通过计算得知,这个底即边界处理表现为:对与L第0行的处理,即text[0]与query各个字符的匹配情况。2.对L第0列的处理,即对于query[0],text各个字符的匹配情况。这样算法的时间复杂度降至O(n^2)
实现如下:
int GetLongestCommSubstrLen(const string& text, const string& query) { int text_len = text.length(); int query_len = query.length(); if (text_len == 0 || 0 == query_len) return 0; vector<vector<int>> L(text_len, vector<int>(query_len, 0)); int text_start = -1; int query_start = -1; for (int j = 0; j < query_len; ++j) { L[0][j] = (text[0] == query[j] ? 1 : 0); } for (int i = 1; i < text_len; ++i) { L[i][0] = (text[i] == query[0] ? 1 : 0); for (int j = 1; j < query_len; ++j) { if (text[i] == query[j]) { L[i][j] = L[i - 1][j - 1] + 1; } } } int longest = 0; for (int i = 0; i < text_len; ++i) { for (int j = 0; j < query_len; ++j) { if (longest < L[i][j]) { longest = L[i][j]; text_start = i - longest + 1; query_start = j - longest + 1; } } } return longest; }这种方法采取了空间换时间的策略,尽管如此,在空间上,还可以优化,在空间的使用上并没有想象的那么恐怖。比如在计算斐波拉契数列时,其实求后一项只与前面两项相关,多余的信息存储造成了空间上的浪费,在这里同样也是如此,看公式L[ i,j ]=L[ i-1,j-1 ] + 1,亦知L的计算也只与前一行相关,而前一行的值是通过计算已知的了,于是只要两行存储空间即可,每当计算新的一行的,把旧行上升到第0行即可,swap一下即可。
改进后的代码如下(也非常简洁):
int GetLongestCommSubstrLen(const string& text, const string& query) { int text_len = text.length(); int query_len = query.length(); if (text_len == 0 || 0 == query_len) return 0; vector<vector<int>> L(2, vector<int>(query_len, 0)); int text_start = -1; int query_start = -1; int longest = 0; for (int j = 0; j < query_len; ++j) { if (text[0] == query[j]) { L[0][j] = 1; } } for (int i = 1; i < text_len; ++i) { L[1][0] = (text[i] == query[0] ? 1 : 0); for (int j = 1; j < query_len; ++j) { if (text[i] == query[j]) { L[1][j] = L[0][j - 1] + 1; if (longest < L[1][j]) longest = L[1][j]; } } L[1].swap(L[0]); } return longest; }
最长公共子串问题(方法一:暴力+RK匹配,方法二:DP+空间优化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。