最长公共子串问题（方法一：暴力+RK匹配，方法二：DP+空间优化）

喜欢ヅ旅行 2022-08-12 00:17 13阅读 0赞

# 时间：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;
    }