Description:

Sandy和Sue的热衷于收集干脆面中的卡片。

然而，Sue收集卡片是因为卡片上漂亮的人物形象，而Sandy则是为了积攒卡片兑换超炫的人物模型。

每一张卡片都由一些数字进行标记，第i张卡片的序列长度为Mi，要想兑换人物模型，首先必须要集够N张卡片，对于这N张卡片，如果他们都有一个相同的子串长度为k，则可以兑换一个等级为k的人物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。

Sandy的卡片数远远小于要求的N，于是Sue决定在Sandy的生日将自己的卡片送给Sandy，在Sue的帮助下，Sandy终于集够了N张卡片，但是，Sandy并不清楚他可以兑换到哪个等级的人物模型，现在，请你帮助Sandy和Sue，看看他们最高能够得到哪个等级的人物模型。

Input：

第一行为一个数N，表示可以兑换人物模型最少需要的卡片数，即Sandy现在有的卡片数

第i+1行到第i+N行每行第一个数为第i张卡片序列的长度Mi，之后j+1到j+1+Mi个数，用空格分隔，分别表示序列中的第j个数

Output：

一个数k，表示可以获得的最高等级。

Sample Input：

Sample Output：

题解：

直接处理处相邻字符的差，转换为字符串匹配的问题。

然后我们对于第一个字符串枚举起点，然后getfail，对于剩下的n-1个字符串KMP一下，然后就可以了。

其实有更快的后缀数组的算法。

我们把所有的字符串拼到一起，中间用最小的特殊字符隔开，求一遍后缀数组，注意求height的时候不能够越过特殊字符。

然后我们二分最后的匹配长度，如果在height中有连续的一段大于或等于这个二分的长度，且这一段中包含了来自于1~n的字符串的后缀，那么这个答案是可行的。

KMP时间复杂度 \(O(nm^2)\)

 

 

后缀数组时间复杂度 \(O(n \times m\ log_2(m\times n))\) （当然线性构造会降到 \(O(n\times m)\) ）

代码如下：