集训队作业average common prefix解题报告ural

1、Average Common Prefix解题福州一中问题简述求一个字符串它本身和它的每个单循环串的 LCP 的平均值。数据规模字符串长=250000算法分析与这题很类似的一个问题的模型无疑就是后缀数组了。所以这题用后缀数组来解也不是什么太难于想到的地方了。问题在于如何实现上。似乎普通的实现方法并不能够承受本题的苛刻数据的考验。因此需要改进。目前据我了解，有三种改进的方法。最快的方法是 bamboo 的。与普通的程序不同的地方在于，他用了 C+的 sort,替换掉了原先的桶排序。他依靠了 C+强大的语言优势，并且摒弃了理论意义上的时间复杂度(他的代码的复杂度应该是 O(n log n log

2、n)的)。其次的方法是 yuhch 的。他采用的方法是遗弃了传统的方法，改而使用了一篇到的 skew 算法。这个方法需要有广博的知识功底。中提方法是最慢的，不过应该是最实用的吧。由于 Pascal 语言的速度较慢，因此我没有办法用类似 bamboo 的方法来做。传统方法是把一个字符“环”拆成“串”，长度由 N 变成了 2N-1，然后用后缀数组来做，处理就可以直接在环上做了：UseIf I + L = N Then V2,I := RElseV2,I := RInstead of：If I + L = N Then方法则是：计算的时候一个元素的两个关键字稍稍I + LI + L - N ;V2,

3、I := RI + LElseV2,I := 0；其中，I 表示串的头，L 表示串长。这应该是不难理解的。因为实际上把它拆成 2N-1 的串实际上处理的方法也是如此。 用这种方法很显然的减小了 1 倍的常数，对于本题的数据刚好能在时限内出解（2.765s）。有时只要附录原题：能够更仔细的分析下题目的性质，问题也许就能迎刃而解。1393. Average Common PrefixTime Limit: 3.0 secondMemory Limit: 16 MBLet T denote some string of length n consisting of capital Latin let

4、ters.Let Shift(T, k) denote the left cyclic shift of T by k-1itions. Thepermuion array for T is an array P1.n sucht Shift(T, P1),Shift(T, P2), ., Shift(T, Pn) is a list of cyclic shifts of T sorted in lexicographical order.Fiven two strings v and w we define LCP(v, w) as the length of theirlongest c

5、ommon prefix. The Average LCP of the string T is the averagelength of longest common prefixbetntwoconsecutiveshifts:Exle, T = MISSISSIPPI, n =11:Average LCP of MISSISSIPPI is1.3InputTheline of the inpontainseger n (1 n 250001). The secondline contains string T.OutputThe only line of the output should contahe Average LCP of T with 3digits after decimal po.iPiShift(T, Pi)LCP111IMISSISSIPP128IPPIMISSISS135ISSIPPIMISS442ISSISSIPPIM051MISSISSIPPI0610PIMISSISSIP179PPIMISSISSI087SIPPIMISSIS294SISSIPPIMIS1106SSIPPIMISSI3113SS