ACM14KP3 - Editorial



Author: Jingbo Shang
Tester: Anudeep Nekkanti
Editorialist: Jingbo Shang




Hash, Suffix Array, Segment Tree


Given two strings s[0…L-1] and t[1…L-1], find out the maximum prefix such that they are cyclic equivalent.


Let F[i] be the largest k, such that s[i…i + k - 1] equals to t[0…k - 1]. Similarly, G[j] denotes the largest k, such that s[0…k-1] equals to t[i…i+k-1]. Both of them could be done by binary search plus hash, or Suffix Array, in O(LlogL) time.

With these two auxiliary arrays, we can rewrite our goal in the following form:

For every 0 <= i < L, we need to find out the maximum j, such that 0 <= j < F[i] and j + G[j] >= i. For such pair <i, j>, the length of prefix is i + j, as illustrated in the following figure.

This query for each i could be solved by Segment Tree, while each node ([l, r]) records the maximum j+G[j] of l <= j <= r. Therefore, this problem could be solved in a a time of O(LlogL).


Solutions will be available soon.

Author’s solution can be found here.
Tester’s solution can be found here.

I found very interesting submission of by sajo775 . What it does is nothing but just using first half part of KMP algorithm that is calculating LPS(Longest proper suffix array) of a+b and b+a and for later half part of both strings it compares for all values of p and checks if that value of p is possible. particular p value is possible only if lps(A+B)[p]+lps(B+A)[p] >=p. It is very very fast. just 0.08 seconds it took. I optimised it a little. My Code: myCode