1. 最长回文串
一般用后缀数组或者后缀树可以解决,
用此方法:http://blog.csdn.net/v_july_v/article/details/6897097
预处理后缀树,使得查询LCA的复杂度为O(1)。这步的开销是O(N),N是单词S的长度 ;
对单词的每一位置i(也就是从0到N-1),获取LCA(S(i), S‘(N-i-1)) 以及LCA(S(i), S’(n-i))。查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每坨i,所以复杂度是O(N) ;(s'是s的翻转串)
找到最大的LCA,我们也就得到了回文的中心i以及回文的半径长度,自然也就得到了最长回文。总的复杂度O(n)。 (在前文......
阅读全文