Baltic Olympiad in Informatics: 2019 Day 2, Problem 2

Jill and Jane are sisters. Last Christmas each of them got a string consisting of colorful beads. We can describe each color as a letter of the English alphabet (a…z), and each string of beads as a word.

The girls would like to create necklaces from their strings. They can turn each string into a necklace by removing some (possibly zero) beads from the ends, and then connecting the ends of the remaining part of the string. The resulting necklace can be rotated and turned over.

The sisters want their necklaces to look exactly the same, and also be as long as possible. What is the maximum length they could achieve?

Input Specification

The first and the second line each contain a non-empty sequence consisting of no more than ~N~ lowercase characters, the descriptions of Jill's and Jane's strings respectively.

Output Specification

The first line should contain a single positive integer: the maximum number of beads each girl's necklace can have in the end. It is guaranteed that a positive length can be achieved.

The second line should contain two integers: the starting positions of the necklaces in Jill's and Jane's string respectively. If there are several possibilities, output any one of them. The positions are numbered left to right starting from 0.

Sample Input

zxyabcd
yxbadctz

Sample Output

4
3 2

Explanation for Sample Output

We can do as follows:
zxyabcd ~\to~ ---abcd
yxbadctz ~\to~ --badc--
The strings abcd and badc result in identical necklaces.

Grading

In this task, your program receives full points for a test group if it correctly finds the longest possible necklaces in all test cases. If it finds in each test case necklaces at least half the length of the longest possible ones, it receives 20% of the points.

The test groups satisfy the following conditions:

1. (~25~ points) ~N = 100~.
2. (~20~ points) ~N = 400~.
3. (~40~ points) ~N = 3000~.

The last group is a special case. It has the same time limit as above, but your solution is allowed to use only 4 MB of memory.