登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

字符串问题实例  

2009-09-25 20:43:40|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/70971767200982584340501/

1.求最长回文子串。
[解法]:
将整个字 符串反过来写在原字符串后面,中间用一个特殊的字符隔开。这样就把问题变为了
求这个新的字符串的某两个后缀的最长公共前缀。而某两个后缀的lcs的计算利用后缀数组,可以O(1),这样总的复杂度就可以降为O(n)。
eg:aabebf  ---->   aabebf&fbebaa

假设存在一个回文串,则它具有如下特点,|------<---*--->--|&|--<---*--->------|
从头图中*处开始的两个后缀的最长公共前缀就是回文串的,这两个*的位置具有特殊性
,如果回文串是奇数长则与&的距离相等,如果是偶数则相差1。这样*的可能位置就是线性的。


2.不相同的子串的个数
[解法]:
根据后缀数组里的顺序我们进行计算,假设前i个后缀所包含的子串数目为,N,我们看加上第i+1个后缀,会增加多少个子串。我们看到这个新加的后缀,它的长度为len-sa[i],它的前缀也就有这些。但是这些前缀里,有已经出现的,个数就是与它相邻后缀的lcs的长度,为height[i],这样我们要从这里面减去它结果就是增加了len-sa[i]-height[i].这样只需要把后缀数组从1扫描到N即可计算出全部结果。

3.可重叠最长重复子串
[解法]:
这个就是后缀数组里,max{lcs(i,i+1)}的大小

4.重复出现但不重叠的最长子串长度(pku1743).
[解法]:
后缀数组,因为如果存在长度为i的不重叠重复子串,也一定存在长度为1...i-1的不重叠重复子串。这样我们就可以用二分长度来做。因此需要一个判断函数:判断是否存在一个长度为L的不重叠重复子串。

这个判断可以这样来做:我们维持一段height的值>= L的区间,并保存这个区间里的在原串中的索引的最大值和最小值,并比较这两个之间的距离是否大于L,这样可以保证它们不重叠,如果这两个重叠的话,那么其他的更必然是重叠的。

5.求一个字符串中出现次数最多的子串。
[解法]:
后缀数组,只需要扫描height数组,找到一个最长的连续序列,这个序列元素不包含0,那么它们的公共前缀就是那个出现次数最多的子串。这里假设子串可以重叠。

6.求一个串的重复次数最多的连续重复子串.(spoj687,pku3693)  
[解法]:
先穷举长度 L ,然后求长度为 L 的子串最多能连续出现几次。首先连续出 现
1 次是肯定可以的,所以这里只考虑至少 2 次的情况。假设在原字符串中连续 出
现 2 次,记这个子字符串为 S ,那么 S 肯定包括了字符 r[0], r[L], r[L*2],
r[L*3], …… 中的某相邻的两个。所以只须看字符 r[L*i] 和 r[L*(i+1)] 往前和
往后各能匹配到多远,记这个总长度为 K ,那么这里连续出现了 K/L+1 次。最 后
看最大值是多少。

这里的关键点在:我们有一个循环节为L的重复串,我们用长度L去分割它,我们可以看到必然有一个L段落到重复串的区间上,以这个L的左右两端点为开始,往左找到一个最大的匹配位置,往右找到一个最大的匹配位置。我们可以看到它们合起来就是整个重复串大小。而往左或者往右寻找匹配位置,时间上是再求L的左右端点开始的后缀的lcs(这个就可以用后缀数组来求解了)。

具体如下:枚举长度L,对于一个已经确定的长度L,我们再穷举r[0], r[L], r[L*2],r[L*3], …… 中的相邻的两个。找到可以扩展到的最大长度,这样就找到了长度为循环节为L的重复最多的连续重复子串。复杂度为N*(N/1+N/2...+N/N)*O(lcs(r[L*i],r[L*(i+1))),lcs这个操作可以利用后缀数组在O(1)时间内解决,所以总的复杂度是O(n*(n/1+n/2...+n/n)) = O(n^2logn)。

7.两个字符串最长公共子串 (pku2774)
[解法]:将s1,s2合并为一个字符串s, 也就是求s的max(lcp[i][j]), 唯一i,j分别位于s1和s2, 利用后缀数组计算s的h[]或者height[]数组,那么答案即为h中的最大值。
证明如下:反证法。s1,s2一定存在最大公共子串t,t为s1的子串t1和s2的子串t2的最长公共前缀的长度lcp[t1][t2], 假设t1,t2在后缀数组中不相邻,则任意取后缀数组中位于t1,t2之间的串tt, 则lcp[tt][t1]与lcp[tt][t2]中至少有一个同时满足

    (1) >=lcp[t1][t2] :(这是由后缀数组的性质所决定的,因为lcp[t1][t2]等于它们两个之间相邻后缀的最小值)
    (2) 两串分别位于s1,s2:这是因为t1,t2分别属于s1,s2;(因为tt要么属于s1,要么属于s2,如果属于s1,则tt,t2分别属于s1,s2,反之则t1,tt分别属于s1,s2)
如果>lcp[t1][t2],这样就与lcp[t1][t2]=max(lcp[i][j]), 唯一i,j分别位于s1和s2,矛盾,因为出现了一个比最大值还大的lcp。所以假设不成立,所以t1,t2在后缀数组中相邻。
如果=lcp[t1][t2],那我们可以把现在的这个作为前后两部分的最长公共子串,这样不断迭代下去,也可以保证,找到一个可行解在后缀数组中相邻。

所以我们只有后缀数组中满足i,i+1一个在s1,一个在s2,并且最大的那个lcp(i,i+1)即可。通过证明s1和s2那个最长公共子串位于后缀数组中的相邻位置,我们把复杂度减低到了线性


8.每个字符串至少出现两次且不重叠的最长子串 (spoj220)
[解法]:
后缀数组。

  评论这张
 
阅读(2346)| 评论(1)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018