logo AlgoBeat OnlineJudge
登录 注册

#103796. [BZOJ 3796] Mushroom追妹纸

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

题目描述

Mushroom 最近看上了一个漂亮妹纸。他选择一种非常经典的手段来表达自己的心意——写情书。考虑到自己的表达能力,Mushroom 决定不手写情书。他从网上找到了两篇极佳的情书,打算选择其中共同的部分。另外 Mushroom 还有个一个情敌 Ertanis,此人也写了封情书给妹子。

Mushroom 不希望自己的情书中完整的出现了情敌的情书(这样抄袭的事情就暴露了)。

Mushroom 把两封情书分别用字符串 来表示,Ertanis 的情书用字符串 来表示,他要截取的部分用字符串 表示。

需满足:

  • 的子串
  • 的子串
  • 不是 的子串
  • 的长度应尽可能大

所谓子串是指:在字符串中连续的一段。

输入格式

输入有三行,第一行为一个字符串 第二行为一个字符串 ,第三行为一个字符串 。输入仅含小写字母,字符中间不含空格。

输出格式

输出仅有一行,为 的最大可能长度,如 不存在,则输出 0

样例

样例输入 #1

abcdef
abcf
bc

样例输出 #1

2

样例解释

的公共子串有 abcabbcabcf,其中 abcbc 包含子串 bc 不合法,所以最长的合法子串为 ab

数据范围与提示

对于 的数据,