ACM14KP3 - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Medium

PREREQUISITES:

Hash, Suffix Array, Segment Tree

PROBLEM:

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

EXPLANATION:

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.

2

I found very interesting submission of https://www.codechef.com/viewsolution/6019739 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