TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1239
  • 题目
  • P1239【USACO OCT09】牛棚回声
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    奶牛们非常享受在牛栏中哞叫,因为她们可以听到她们哞声的回音。虽然有时候并不能完全听到完整的回音。Bessie曾经是一个出色的秘书,所以她精确地记录了所有的哞叫声及其回声。她很好奇到底两个声音的重复部份有多长。
      输入两个字符串(长度为1到80个字母),表示两个哞叫声。你要确定最长的重复部份的长度。两个字符串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串。
      我们通过一个例子来理解题目。考虑下面的两个哞声:
      moyooyoxyzooo
      yzoooqyasdfljkamo
      第一个串的最后的部份"yzooo"跟第二个串的第一部份重复。第二个串的最后的部份"mo"跟第一个串的第一部份重复。所以"yzooo"跟"mo"都是这2个串的重复部份。其中,"yzooo"比较长,所以最长的重复部份的长度就是5。

    输入格式

    共两行:每一行是1个字符串表示奶牛的哞声或它的回声

    输出格式

    有一行为一个单独的整数表示输入的2个字符串中,一个字符串的前缀和另一个字符串的后缀的最长的重复部份的长度。

    样例输入

    abcxxxxabcxabcd
    abcdxabcxxxxabcx

    样例输出

    11

    提示

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


    来源  USACO OCT09