当前位置:首页 > 字符串 > 后缀数组 > 正文
SSOJ2293公共子串
2882+

题目大意:n个字符串,最长公共连续的子序列长度是多少?(公共不要求全部都有,只需要过半的字符串包含就行)

题目描述

输入n个小写字母组成的DNA序列,你的任务是求出一个长度最大的字符串,使得它在超过一半的DNA序列中出现。如果有多解,按照字典序从小到大输出所有解,无解输出’?’。

输入

第一行一个数n,接下来n行,每行一个由小写字母组成的字符串。

输出

见题目描述。

样例输入

样例1
3
abcdefg
bcdefgh
cdefghi

样例2
3
xxx
yyy
zzz

样例输出

样例1
bcdefg
cdefgh

样例2
?

提示

n不大于100,每个字符串长度不超过1000。

每个输入输出文件的大小不超过1MB。

数据已重新制作。

《高级数据结构》例题11-2

来源:Waterloo Local Contest 2006

解题思路

后缀数组的一个应用就是求字符串的最长连续子序列。i是第i串的开头位置,p[i]是排名为i的串的开头位置,g[i]是排名为i的字符串与前一名次的字符串的最长公共前缀长度。

假设我们已经求出g[i],那么通过遍历g[1]到g[n],如果出现超过“连续过半”个“长度相同”的,那么该长度就是答案,长度越大越好,我们可以二分长度,找满足条件的最大长度。

1、长度相同:因为g[i]记录的是最长长度,所以并不要求相同,可以更大;如验证长度为m是否过半,只要g[i]>=m,都是可以的,我们只看后缀的前m个字符而已;

2、连续:一定要连续,如果不连续“长度相同”,中间夹着一个g[i]<m的话,那么g[i]以及它前后的串的前m个都是不相同的;

3、过半:一个有c个串,那么要有c/2+1串才符合要求;遍历过程中,可能出现同一个串包含特定前缀多次,为避免同一串统计多次,统计过需要标记一下(可以用时间戳、退栈,不建议memset,数组很大,太浪费时间了)。

下面我们思考,如果求g数组???

1、暴力:相邻排名的串逐个字符比较,时间复杂度O(n*n),应该会超时;

2、哈希+二分:时间复杂度O(nlogn),但哈希总有一点点概率会出错,而且代码不好写;

3、后缀数组+思考:想通了,代码很好写,时间复杂度O(n)。

假设现在已经得到后缀数组,其中p[i]表示排名为i的串,r[i]表示i串的排名,g[i]表示排名为i的串和排名为i-1的串的最长公共前缀的长度,h[i]表示i串与前一名次的串(k串)的最长公共前缀的长度,那么g[ r[i] ] = h[i],因为大家都表示排名为r[i]的串与前一名次的串的最长公共前缀的长度,而且h[i] >= h[i-1],这个条件很关键,可以避免重复计算,下面简单证明一下:

i-1串与k串(i-1串的前一名)的最长公共前缀长度是h[i-1],根据字符串的开头s[i-1]和s[k]进行分类讨论:

1、开头不相同,s[i-1] != s[k],因为没有公共前缀,所以h[i-1] = 0,此时h[i] >= h[i-1]

2、开头相同,s[i-1] == s[k],此时继续比较s[i]和s[k+1],如果相同继续比较下去。i串和k+1串最长公共前缀是多少呢?少了首字符,即h[i-1]-1。因为k串排在i-1串前面,所以k+1

串排在i串前面;按照排名来算,k+1串(不妨设排名为x)到i串(不妨设排名为y)之间的最长公共前缀的长度,就是g[x+1]到g[y]的最小值(<=g[y]、中间每个都有这样的前缀);因为y=p[i],所以g[ p[i] ] = h[i] >= h[i-1] – 1。

程序实现

下面解释一下代码:

12-32:验证是否存在过半的字符串存在连续m个相同,存在的话将相同字符串的其中一个放入d数组。

35-40:读入c个字符串,将原有字符转成ascii的1到26,因为间隔需要放入不同的字符,而且间隔要互不相同,因为间隔相同,计算公共长度很可能把间隔算进去,除非再记录每个字符串的首位位置、长度?(读入时,还需要记录各个位置属于哪一次,这样可以方便后面去重、扩大字符范围也能做)

41-43:索引排序,得到后缀数组,觉得不保险,可以写倍增、基数排序。

44-49:求g数组,第i串与前一名次(排名r[i]-1)的串(j串)进行逐个字符比较,得到最大公共前缀长度h[i] = k,因为下一次h[i+1]>=k-1,前面k-1个不用在比较,但是k需要先-1。求g的话,写上g[ p[i] ] = h[i] = k就行,其实h[i]可以不写,只是方便初学者理解。

51-55:二分搜索得到最大长度x;56-65:输出结果。

SSOJ2293公共子串:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!