시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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?

입력

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.

출력

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.

제한

  • N = 100, 400, 3000

예제 입력 1

zxyabcd
yxbadctz

예제 출력 1

4
3 2

We can do as follows:

“zxyabcd” → “---abcd”
“yxbadctz” → “--badc--”

The strings “abcd” and “badc” result in identical necklaces.