Two strings a[0..n-1] and b[0..n-1] are called cyclic equivalent if and only if there exists an offset d, such that for all 0 <= i < n, a[i] = b[(i + d) mod n].
Given two strings s[0..L-1] and t[0..L-1] with same length L. You need to find the maximum p such that s[0..p-1] and t[0..p-1] are cyclic equivalent.Print 0 if no such valid p exists.
The first line contains an integer T indicating the number of test cases.
For each test case, there are two lines in total. The first line contains s. The second line contains t.
All strings contain only lower case alphabets.
Output T lines in total. Each line should start with "Case #: " and followed by the maximum p. Here "#" is the number of the test case starting from 1.
- 1 ≤ T ≤ 10
- 1 ≤ L ≤ 1000000
Input: 2 abab baba abab baac Output: Case 1: 4 Case 2: 3
Case 1, d can be 1.
Case 2, d can be 2.
|Tags||acmkgp14, admin, hashing, medium, segment-tree, suffix-array|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions