题目背景

译自 BalticOI 2019 Day2 T2. Necklace

题目描述

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

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

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

输入格式

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

输出格式

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

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

zxyabcd
yxbadctz

4
3 2

提示

样例解释

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

zxyabcd $\to$ ---abcd
yxbadctz $\to$ --badc--

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

评分标准

如果你的程序得到的项链合法（即两条项链等价），且长度与可能的最长项链长度相等，你将得到该测试点全部的分数。

如果你的程序得到的项链合法，且长度达到了最长项链长度的一半，你将得到该测试点 $20\%$ 的分数。

请注意，你在一个子任务上的得分，等于你在该子任务所有测试点的最低得分。

子任务

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

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

前三个子任务内存限制均为 1GB。