题目大意：n个字符串，最长公共连续的子序列长度是多少？（公共不要求全部都有，只需要过半的字符串包含就行）

题目描述

输入

输出

样例输入

样例1
3
abcdefg
bcdefgh
cdefghi

样例2
3
xxx
yyy
zzz

样例输出

样例1
bcdefg
cdefgh

样例2
?

提示

解题思路

后缀数组的一个应用就是求字符串的最长连续子序列。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：输出结果。