Necklace 4
시간 제한2초메모리 제한8 MB
두 문자열에서 양끝을 잘라낸 부분 문자열 중, 원형으로 회전하거나 뒤집었을 때 서로 같은 것을 찾아 최대 길이와 위치를 구한다.
문제
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 = 3000