### PROBLEM LINK:

**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.