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).
AUTHOR’S AND TESTER’S SOLUTIONS:
Solutions will be available soon.
Author’s solution can be found here.
Tester’s solution can be found here.