ICPC North Central NA Contest 2018 A. Pokegene 后缀数组解法

陆陆续续调了3天上午,终于调出来了。 这题题解给的代码是错的。 错在:每个字符要加上一个’\0′,这样可以处理:bb,bba这种情况. 下面说下这题的思路: 先不考虑算法。 对于一个询问,把k个字符串进行按字典序排序。 位置相近的字符串肯定LCP越大。 所以恰好L个字符串有LCP,且其他没有,一定是排序后的连续L个。 我们排序后枚举每个位置[i,i+L-1] 看看LCP(i,–,i-L+1),这么些字符串的LCP是多少,然后减去max(LCP(i-1,......i,-L+1),LCP(i,......i,-L+2))。 这样得到的结果即:[i,i-L+1]的LCP,且其他字符串前缀没有,的个数。 然后多个字