回文串是一种“对称”的字符串,若字符串 是一个回文串,则 满足 ,其中 表示字符串 的翻转。
cyy非常喜欢回文串,今天他掏出了一个构造回文串的算法:
-
在第 步,字符串为 。
-
在第 步,字符串为 ,其中 表示字符串之间的连接。
上述算法中的 表示一个未知字符,这样的字符一共有 种,分别为 。
就在cyy开心地构造着回文串时,毒瘤的JM想起了最长公共子串问题,和这个回文串结合了一下,弄出了一道毒瘤(其实并不)题:
为便于描述,规定 表示 的子串 ,其中 表示 的第 个字符,且 ,其中 表示 的长度。例如 abcde
,则 bc
。
给定 次询问,每次给定五个正整数 ,求 的两个子串 和 的最长公共子串的长度是多少。
例如 ,则 abacaba
,那么:
和 的最长公共子串为a
,其长度为 ;
和 的最长公共子串为ab
或ac
,其长度为 。