存档

文章标签 ‘最长重复子串’

最长公共子序列|最长公共子串|最长重复子串|最长不重复子串|最长回文子串|最长递增子序列|最大子数组和

2012年6月27日 1 条评论

---

最近练手,整理了一个“最”系列的主题,这些题目有点绕,个别的还有别名(详见博文),混在一块比较乱,就索性放在一起做了个整理,区别的时候要注意子序列与子串的不同,前者不要求连续,后者要求连续;由于大部分跟DP有关,有的还可以渐进寻求多种解法,可以用来做不错的练手。

下面是这些问题的博文目录

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

=1=最长公共子序列(LCS)==

=2=最长公共子串==

=3=最长重复子串==

=4=最长不重复子串==

=5=最长回文子串==

=6=最长递增子序列(LIS)==

=7=最大子数组和(连续子数组最大和)==

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

总结:

  1. 问题分类
    • 前两个是关于两个字符串的问题、中间三个是关于单个字符串的问题,最后两个是数组相关的问题;不过不一定绝对,例如最长公共子序列也可以是数组问题;
    • 从解决方案看,12属于“二维”DP问题,因为是两个对象间的问题;467属于“一维”DP问题,是单个对象的问题;345又是后缀数组的典型应用。
  2. 为练手,对大多数问题,尽量逐步探索,整理了多种思路,例如在最长不重复子串问题中,我逐步优化,尝试了四种实现方法,并成功得到了时间为O(N),辅助空间为常数的方案,回头反思,发现其优化的思维得益于对最大子数组和以及LIS的整理与思考。
  3. 这些问题之间相互有很多相通的地方,例如,在最长不重复子串问题中,其DP思路与最长递增子序列有点类似,二者同属“一维”的问题,并且都需要记录当前元素“之前”的某些信息;而在DP优化过程中,最长不重复子串问题又与最大子数组和的优化同出一辙,这两个“一维”的DP问题都只使用O(1)的空间便可以记录子问题的最优解,这种“便捷”的方案并不是空穴来风,而是先通过“规规矩矩”的DP一步步探索,才发现这种“trick”的存在,很是有意思。

勘误:

  • 本系列文章所有代码出现 char xx  [256] 的地方改为 int xx [256] ,因为从逻辑上讲char xx[256] 是有可能出问题的。(感谢HFC

阅读全文...

最长重复子串

2012年6月25日 5 条评论

---

首先这是一个单字符串问题。子字符串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);
}

阅读全文...