#10318. [USACO09OCT]Barn Echoes G

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: stardustamy

题目描述

奶牛们非常享受在牛栏中哞叫,因为她们可以听到她们哞声的回音。虽然有时候并不能完全听到完整的回音。Bessie 曾经是一个出色的秘书,所以她精确地纪录了所有的哞叫声及其回声。她很好奇到底两个声音的重复部份有多长。

输入两个字符串(长度为 1 10^6 个字母),表示两个哞叫声。你要确定最长的重复部份的长度。两个字符串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串。

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

moyooyoxyzooo

yzoooqyasdfljkamo

第一个串的最后的部份 "yzooo" 跟第二个串的第一部份重复。第二个串的最后的部份 "mo" 跟第一个串的第一部份重复。所以 "yzooo" 跟 "mo" 都是这 2 个串的重复部份。其中,"yzooo" 比较长,所以最长的重复部份的长度就是 5

输入格式

  • Lines 1..2: Each line has the text of a moo or its echo

输出格式

  • Line 1: A single line with a single integer that is the length of the longest overlap between the front of one string and end of the other.

样例

abcxxxxabcxabcd
abcdxabcxxxxabcx

11

数据范围与提示

'abcxxxxabcx' 既是第一个字符串的前缀也是第二个字符串的后缀。

字符串的长度不超过 10^6