BalticOI 2019 Day2 T2. Necklace

题目描述

Jill 和 Jane 是姐妹，去年圣诞节她们每个人都得到了一串彩色珠子。我们可以将每种颜色描述为小写英文字母（$\texttt{a}\ldots \texttt{z}$），并将每串珠子描述为一个单词。

女孩们想从她们的珠子中创造项链。她们可以从自己的那串珠子的两端移除一些珠子（可能为零），然后连接剩余部分的两端，将其变成项链。生成的项链可以旋转和翻转。

姐妹们希望她们的项链看起来完全一样，并且尽可能长。她们项链可以达到的最大长度是多少？

输入格式

输入包含两行，每行一个字符串，分别描述了 Jill 和 Jane 的一串彩珠。

输出格式

输出第一行应该包含一个正整数，代表项链的长度。测试数据保证存在长度为正整数的项链。

第二行包含两个正整数，分别代表 Jill 和 Jane 得到的项链在原来彩珠串中的起始位置，如果有多种合法方案，任意输出一种即可。每一串彩珠从左到右从 $0$ 开始编号。

样例

输入

zxyabcd
yxbadctz

输出

4
3 2

我们对两串彩珠进行如下处理：

• $\texttt{zxyabcd} \to \texttt{---abcd}$
• $\texttt{yxbadctz} \to \texttt{--badc--}$

最终得到的两串项链 $\texttt{abcd}$ 和 $\texttt{badc}$ 经过翻转和旋转后是等价的。

数据范围与提示

评分标准

• 如果你的程序得到的项链合法（即两条项链等价），且长度与可能的最长项链长度相等，你将得到该测试点全部的分数。
• 如果你的程序得到的项链合法，且长度达到了最长项链长度的一半，你将得到该测试点 $20\%$ 的分数。
• 请注意，你在一个子任务上的得分，等于你在该子任务所有测试点的最低得分。

子任务

设输入中每个字符串的长度上限为 $N$。

• 子任务 1（$25$ 分）：$N = 100$
• 子任务 2（$20$ 分）：$N = 400$
• 子任务 3（$40$ 分）：$N = 3000$
• 子任务 4（$15$ 分）：$N = 3000$，内存限制为 $3$ MB。