[SPOJ 220]

Relevant Phrases of Annihilation

后缀数组

给出最多10个字符串,每个字符串长度最多10,000,求这样一个子串的长度:
(1) 在每个字符串中非重叠地出现了两次;
(2) 长度最长。

可以将10个字符串连接在一起,其中每个连接位置用一个大于128的唯一值来隔开不同字符串,然后求后缀数组。随后,可以二分答案,对于某个长度值m,判断:对于h数组中值>=m的某连续区间内,求每个子串对应的原字符串最左和最右子串的位置,若每个字符串中左右子串的位置差>=m,即两个子串非重叠,return 1。而每次某区间内无法满足时,直接从该区间下一个位置开始检查h数组。由此对于每个长度值进行判断的时间复杂度是O(n)的,这里n是后缀数组的长度,最多100,000。总体时间复杂度便是O(nlgn)的。

很好的题目……这题也是罗穗骞论文里推荐的最后一道例题了。虽然还是没太看懂他的DA和DC3,不过确实学到了很有趣的知识。

ps:也推荐一个最近发现的汽车网站:38号测试中心