3213 - 听取叽声一片

题目描述

小胡虽然在儿童节小挣了一笔,但是记录过消费后,他发现自己得开源节流了。所以他买了好多只小鸡仔,通过养鸡来增加收入。

但是这些小鸡实在是太吵了,整天叽叽叽个不停,小胡被吵得神经衰弱,都快产生幻听了,只觉得一串一串的回声在脑子里盘旋。

声音化作了两串字符串,表示他听到的叽叽声,两串声音中最长的重复部分就是他的幻听。

最长重复部分指的是:从一个字符串第一个字符开始的连续字符串和从另一个字符串最后一个字符开始的连续字符串,完全相同的最大长度。

例如以下两串叽叽声:

aNBHhjsada

jsadasdfdfdfdfdaNB

第一个字符串的前缀 aNB 和第二个字符串的后缀相同;

第一个字符串的后缀 jsada 和第二个字符串的前缀相同;

jsada 比较长,所以最长的重复部分长度为 5

输入

输入两行字符串表示叽叽声,不包含空格。

输出

输出一个整数,表示最长的重复部份的长度。

样例

输入

abcdabcde
defgfhabcdab

输出

6

输入

abcd
daab

输出

2
说明

【样例 1 解释】

第一个字符串的前缀 abcdab 和第二个字符串的后缀相同。

第一个字符串的后缀 de 和第二个字符串的前缀相同。

abcdab 比较长,所以最长的重复部分长度为 6

【数据范围】

读入的两个字符串长度为 180 个字母。

来源

东方博宜OJ

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 354
通过人数 186
金币数量 0 枚
难度 入门


上一题 下一题