P6229 [BalticOI 2019] Necklace (Day2)

**Translated from [BalticOI 2019](http://boi2019.eio.ee/tasks/) Day2 T2.** ***[Necklace](http://boi2019.eio.ee/wp-content/uploads/2019/05/necklace.en_.pdf)***

Jill and Jane are sisters. Last Christmas, each of them received a string of colored beads. We can describe each color by a lowercase English letter ($\texttt{a}\ldots \texttt{z}$), and describe each bead string as a word. The girls want to make necklaces from their bead strings. Each of them may remove some beads from both ends of her own string (possibly zero), and then connect the two ends of the remaining part to turn it into a necklace. The resulting necklace can be rotated and flipped. The sisters want their necklaces to look exactly the same and be as long as possible. What is the maximum possible length of their necklaces?

The input contains two lines, each with a string, describing Jill’s and Jane’s bead strings.

The first line should contain a positive integer, the length of the necklace. The testdata guarantees that a necklace of positive length exists. The second line contains two positive integers, representing the starting positions of Jill’s and Jane’s necklaces in the original bead strings. If there are multiple valid solutions, output any one. Each bead string is indexed from left to right starting from $ 0 $.

### Sample Explanation We process the two bead strings as follows: `zxyabcd` $ \to $ `---abcd` `yxbadctz` $ \to $ `--badc--` In the end, the two necklaces `abcd` and `badc` are equivalent after flipping and rotation. ### Scoring If your program produces valid necklaces (i.e., the two necklaces are equivalent) and the length equals the maximum possible necklace length, you will get the full score for that test point. If your program produces valid necklaces and the length reaches at least half of the maximum possible necklace length, you will get $ 20\% $ of the score for that test point. **Note that your score on a subtask equals the minimum score among all test points in that subtask.** ### Subtasks Let the maximum length of each input string be $ N $. - Subtask 1 (25 points): $ N = 100 $. - Subtask 2 (20 points): $ N = 400 $. - Subtask 3 (40 points): $ N = 3000 $. - Subtask 4 (15 points): $ N = 3000 $, **memory limit is 3 MB**. The memory limit for the first three subtasks is 1 GB. Translated by ChatGPT 5