首页 > 算法 数据结构 > 最长公共子串(Longest-Common-Substring,LCS)

最长公共子串(Longest-Common-Substring,LCS)

2012年6月25日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

这个LCS跟前面说的最长公共子序列的LCS不一样,不过也算是LCS的一个变体,在LCS中,子序列是不必要求连续的,而子串则是“连续”的。即:

题:给定两个字符串X,Y,求二者最长的公共子串,例如X=[aaaba],Y=[abaa]。二者的最长公共子串为[aba],长度为3。

本节给出三种不同的实现方式,并对比分析每种方法的复杂度,内容如下:

==基本算法==

==DP方案==

==后缀数组==

==各方法复杂度分析==

==================================

基本算法

其实对于最长公共子串,还是比较简单易想的,因为子串是连续的,这就方便了很多。最直接的方法就是用X每个子串与Y的每个子串做对比,求出最长的公共子串。代码如下:

/* 最长公共子串 Longest Common Substring */

int maxlen;    /* 记录最大公共子串长度 */
int maxindex;  /* 记录最大公共子串在串1的起始位置 */
void outputLCS(char * X);  /* 输出LCS */

/* 最长公共子串 基本算法 */
int comlen(char * p, char * q)
{
	int len = 0;
	while(*p && *q && *p++ == *q++)
	{
		++len;
	}
	return len;
}

void LCS_base(char * X, int xlen, char * Y, int ylen)
{
	for(int i = 0; i < xlen; ++i)
	{
		for(int j = 0; j < ylen; ++j)
		{
			int len = comlen(&X[i],&Y[j]);
			if(len > maxlen)
			{
				maxlen = len;
				maxindex = i;
			}
		}
	}
	outputLCS(X);
}

==================================

DP方案

既然最长公共子串是最长公共子序列的变体,那么最长公共子串是不是也可以用动态规划来求解呢?

我们还是像之前一样“从后向前”考虑是否能分解这个问题,在最大子数组和中,我们也说过,对于数组问题,可以考虑“如何将arr[0,...i]的问题转为求解arr[0,...i-1]的问题”,类似最长公共子序列的分析,这里,我们使用dp[i][j]表示 以x[i]和y[j]结尾的最长公共子串的长度,因为要求子串连续,所以对于X[i]与Y[j]来讲,它们要么与之前的公共子串构成新的公共子串;要么就是不构成公共子串。故状态转移方程

  1. X[i] == Y[j],dp[i][j] = dp[i-1][j-1] + 1
  2. X[i] != Y[j],dp[i][j] = 0

对于初始化,i==0或者j==0,如果X[i] == Y[j],dp[i][j] = 1;否则dp[i][j] = 0。

代码如下:

/* 最长公共子串 DP */
int dp[30][30];

void LCS_dp(char * X, int xlen, char * Y, int ylen)
{
	maxlen = maxindex = 0;
	for(int i = 0; i < xlen; ++i)
	{
		for(int j = 0; j < ylen; ++j)
		{
			if(X[i] == Y[j])
			{
				if(i && j)
				{
					dp[i][j] = dp[i-1][j-1] + 1;
				}
				if(i == 0 || j == 0)
				{
					dp[i][j] = 1;
				}
				if(dp[i][j] > maxlen)
				{
					maxlen = dp[i][j];
					maxindex = i + 1 - maxlen;
				}
			}
		}
	}
	outputLCS(X);
}

==================================

后缀数组

前面提过后缀数组的基本定义,与子串有关,可以尝试这方面思路。由于后缀数组最典型的是寻找一个字符串的重复子串,所以,对于两个字符串,我们可以将其连接到一起,如果某一个子串s是它们的公共子串,则s一定会在连接后字符串后缀数组中出现两次,这样就将最长公共子串转成最长重复子串的问题了,这里的后缀数组我们使用基本的实现方式。

值得一提的是,在找到两个重复子串时,不一定就是X与Y的公共子串,也可能是X或Y的自身重复子串,故在连接时候我们在X后面插入一个特殊字符‘#’,即连接后为X#Y。这样一来,只有找到的两个重复子串恰好有一个在#的前面,这两个重复子串才是X与Y的公共子串。

代码如下:

/* 最长公共子串 后缀数组 */
char * suff[100];

int pstrcmp(const void *p, const void *q)
{
	return strcmp(*(char**)p,*(char**)q);
}

int comlen_suff(char * p, char * q)
{
	int len = 0;
	while(*p && *q && *p++ == *q++)
	{
		++len;
		if(*p == '#' || *q == '#')
		{
			return len;
		}
	}
	return 0;
}

void LCS_suffix(char * X, int xlen, char * Y, int ylen)
{
	int suf_index = maxlen = maxindex = 0;

	int len_suff = xlen + ylen + 1;
	char * arr = new char [len_suff + 1];  /* 将X和Y连接到一起 */
	strcpy(arr,X);
	arr[xlen] = '#';
	strcpy(arr + xlen + 1, Y);

	for(int i = 0; i < len_suff; ++i)  /* 初始化后缀数组 */
	{
		suff[i] = & arr[i];
	}

	qsort(suff, len_suff, sizeof(char *), pstrcmp);

	for(int i = 0; i < len_suff-1; ++i)
	{
		int len = comlen_suff(suff[i],suff[i+1]);
		if(len > maxlen)
		{
			maxlen = len;
			suf_index = i;
		}
	}
	outputLCS(suff[suf_index]);
}

下面给出三种实现方案所用到的打印输出LCS程序以及测试用例程序。

/* 输出LCS
 * 在后缀数组方法中,maxindex=0
 * 因为传进来的就是后缀数组suff[],从0打印maxlen个字符
 */
void outputLCS(char * X)
{
	if(maxlen == 0)
	{
		printf("NULL LCS\n");
		return;
	}
	printf("The len of LCS is %d\n",maxlen);

	int i = maxindex;
	while(maxlen--)
	{
		printf("%c",X[i++]);
	}
	printf("\n");
}

void main()
{
	char X[] = "aaaba";
	char Y[] = "abaa";

	/* 基本算法 */
	LCS_base(X,strlen(X),Y,strlen(Y));

	/* DP算法 */
	LCS_base(X,strlen(X),Y,strlen(Y));

	/* 后缀数组方法 */
	LCS_suffix(X,strlen(X),Y,strlen(Y));
}

==================================

各方案复杂度对比

设字符串X的长度为m,Y的长度为n,最长公共子串长度为l。

对于基本算法,X的子串(m个)和Y的子串(n个)一一对比,最坏情况下,复杂度为O(m*n*l),空间复杂度为O(1)。

对于DP算法,由于自底向上构建最优子问题的解,时间复杂度为O(m*n);空间复杂度为O(m*n),当然这里是可以使用滚动数组来优化空间的,滚动数组在动态规划基础回顾中多次提到。

对于后缀数组方法,连接到一起并初始化后缀数组的时间复杂度为O(m+n),对后缀数组的字符串排序,由于后缀数组有m+n个后缀子串,子串间比较,故复杂度为O((m+n)*l*lg(m+n)),求得最长子串遍历后缀数组,复杂度为O(m+n),所以总的时间复杂度为O((m+n)*l*lg(m+n)),空间复杂度为O(m+n)。

总的来说使用后缀数组对数据做一些“预处理”,在效率上还是能提升不少的。

本节相关代码可以到这里下载。

(全文完)

勘误:(感谢 @jiawei)

后缀数组方法comlen_suff的实现逻辑上有错误,要保证找到公共子串后二者只有一个#号,这样才表示来自不同的字符串,勘误代码如下:

int comlen_suff(char * p, char * q)
{
	int len = 0;
	while(*p && *q && *p++ == *q++)
	{
		++len;
		if(*p == '#' || *q == '#')
		{
			break;
		}
	}
	int count = 0;
	while(*p)
	{
		if(*p++ == '#')
		{
			++count;
			break;
		}
	}
	while(*q)
	{
		if(*q++ == '#')
		{
			++count;
			break;
		}
	}
	if(count == 1)
		return len;
	return 0;
}
  • wangshu123

    int comlen_suff(char* p, char* q, char* mid)
    {
    if((p > mid && q > mid) || (p < mid && q < mid))
    return 0;
    int len = 0;
    while(*p && *q && *p++ == *q++)
    ++len;
    return len;
    }

    这样子可以简单一些吧

  • 3kkkk

    x[i],y[j]的最长公共子串是d[i][j]时,不管x[i]是否等于y[j],x[i-1]y[j-1]的最长公共子串好像不一定是d[i-1][j-1]吧? 这样X[i] == Y[j],dp[i][j] = dp[i-1][j-1] + 1 这个就不对了啊。

    • Yx.Ac

      这里的状态方程是这样的含义:dp[i][j]表示"以x[i]和y[j]结尾"的最长公共子串的“长度”,而且子串是要求连续的,您可以再理解一下。欢迎继续交流 :-)

  • Yx.Ac

    恩,谢谢帮忙指出错误,dp[i][j]表示的就是 以x[i]和y[j]结尾的最长公共子串的长度@靖难

  • http://stackpop.org 靖难

    dp[i][j]表示的是x[1 to i ] 和y[1 to j]的最长公共子串
    那么在x[i]不等于y[j]的时候就代表dp[i][j]等于0?

    最终的结果中,dp[i][j] >= dp[i-1][j-1]这个在任何条件下都是成立的吧,因为是包含关系。

    这里的dp[i][j]表示的应该是 以x[i]和y[j]结尾的最长公共子串的长度?

  • Yx.Ac

    恩,谢谢你,这个不用重新考虑,是我实现的有错误,请见本文末的勘误@jiawei

  • jiawei

    jiawei :
    后缀数组方法中:
    如果都属于X(前面)数组,是不是不能很好的判断出来呢!

    补充下:感觉不是太严谨比方说:X=“aaaaaa”, Y = "ab" 输出结果会错误,以为X的子串此时可以遍历到'#',也就是对X是全部相等的字符时要另行考虑下