首页 > 算法 数据结构 > 最长重复子串

最长重复子串

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

---

首先这是一个单字符串问题。子字符串R 在字符串L 中至少出现两次,则称R 是L 的重复子串。重复子串又分为可重叠重复子串和不可重叠重复子串,这里只是简单讨论最长可重叠的重复子串,给出基本算法和基于后缀数组的算法;关于后缀数组,这里也只是用最简单的形式实现,对于后缀数组的倍增算法和DC3算法的实现以及不可重叠重复子串的问题可参见算法合集之《后缀数组——处理字符串的有力工具》,以后再整理这几个问题。

最直接的方法就是子串和子串间相互比较,这样查看所有的子串对,时间复杂度为O(n^2),代码如下:

/* 最长重复子串 Longest Repeat Substring */

int maxlen;    /* 记录最长重复子串长度 */
int maxindex;  /* 记录最长重复子串的起始位置 */
void outputLRS(char * arr);  /* 输出LRS */

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

void LRS_base(char * arr, int size)
{
	for(int i = 0; i < size; ++i)
	{
		for(int j = i+1; j < size; ++j)
		{
			int len = comlen(&arr[i],&arr[j]);
			if(len > maxlen)
			{
				maxlen = len;
				maxindex = i;
			}
		}
	}
	outputLRS(arr);
}

第二种方法便是采用《编程珠玑》上介绍的“后缀数组”,这个结构是一个字符指针数组,记录目标字符串的所有后缀的起始地址,例如banana这个单词的后缀数组为:


suff[0]:banana

suff[1]:anana

suff[2]:nana

suff[3]:ana

suff[4]: na

suff[5]: a

如果某个子串在目标字符串中出现两次,那么它必将出现在两个不同的后缀中,因此对后缀数组进行排序,以寻找相同的后缀,然后扫描数组,比较相邻的元素便可以找出最长的重复子串。代码如下:

/* 最长重复子串 后缀数组 */
char * suff[30];

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

void LRS_suffix(char * arr, int size)
{
	int suff_index = maxlen = maxindex = 0;

	for(int i = 0; i < size; ++i) /* 初始化后缀数组 */
	{
		suff[i] = & arr[i];
	}
	qsort(suff, size, sizeof(char *), pstrcmp); /* 排序后缀 */
	for(int i = 0; i < size-1; ++i)  /* 寻找最长重复子串 */
	{
		int len = comlen(suff[i],suff[i+1]);
		if(len > maxlen)
		{
			maxlen = len;
			suff_index = i;
		}
	}
	outputLRS(suff[suff_index]);
}

最后给出输出程序和测试用例:

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

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

void main()
{
	char X[] = "banana";

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

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

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

(全文完)

参考资料:

编程珠玑》15.2

  • Yx.Ac

    这里是要进行字符串内各个字母顺序排序啊,(const char**)是没问题的,但是(const char*)就不对了,具体可google qsort的比较函数的用法@JJason

  • JJason

    你好 请问为什么我将pstrcmp 里面的strcmp(*(char **)p, *( char **)q)中的*(char **) 换成(const char *) 会导致结果出错啊

  • Yx.Ac

    恩,也可以这样理解,不过无关紧要,只能说是n2的常数倍吧,因为一般来讲,comlen的期望比较长度是非常短的,推荐字符串排序新探索-基数排序 那里面对字符串比较的期望长度做了一个小推导@鼻子很帅的猪

    • 鼻子很帅的猪

      哦哦 ,明白了 ,thanks

  • 鼻子很帅的猪

    HELLO,有个小错误吧,暴力方法(第一种方法)的时间复杂度应该是O(N3)吧?