#2817. 牛棚回声

牛棚回声

题目描述

奶牛们灰常享受在牛栏中哞叫,因为她们可以听到她们哞声的回音。虽然有时候并不能完全听到完整的回音。

Bessie\red{Bessie}曾经是一个出色的秘书,所以她精确地纪录了所有的哞叫声及其回声。她很好奇到底两个声音的重复部份有多长。

输入两个字符串(长度为1\red{1}80\red{80}个字母),表示两个哞叫声。你要确定最长的重复部份的长度。

两个字符串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串。

我们通过一个例子来理解题目。考虑下面的两个哞声:

moyooyoxyzooo
yzoooqyasdfljkamo

第一个串的最后的部份"yzooo\red{yzooo}"跟第二个串的第一部份重复。第二个串的最后的部份"mo\red{mo}"跟第一个串的第一部份重复。

所以"yzooo\red{yzooo}"跟"mo\red{mo}"都是这2\red{2}个串的重复部份。其中,"yzooo\red{yzooo}"比较长,所以最长的重复部份的长度就是5\red{5}

输入格式

两行: 每一行是1\red{1}个字符串表示奶牛的哞声或它的回声。

输出格式

第一行:

包含一个单独的整数表示输入的2\red{2}个字符串中,一个字符串的前缀和另一个字符串的后缀的最长的重复部份的长度。

样例

输入样例

abcxxxxabcxabcd
abcdxabcxxxxabcx

输出样例

11

提示

"abcxxxxabcx\red{abcxxxxabcx}"是第一个字符串的前缀和第二个字符串的后缀。

统计

相关

在下列比赛中:

搜索