Mushroom追妹纸

时间限制:10s      空间限制:256MB

题目描述

Mushroom最近看上了一个漂亮妹纸。他选择一种非常经典的手段来表达自己的心意——写情书。考虑到自己的表达能力,Mushroom决定不手写情书。他从网上找到了两篇极佳的情书,打算选择其中共同的部分。另外,Mushroom还有个一个情敌Ertanis,此人也写了封情书给妹子。
Mushroom不希望自己的情书中完整的出现了情敌的情书。(这样抄袭的事情就暴露了)。
Mushroom把两封情书分别用字符串s1和s2来表示,Ertanis的情书用字符串s3来表示,他要截取的部分用字符串w表示。
需满足:
1、w是s1的子串
2、w是s2的子串
3、s3不是w的子串
4、w的长度应尽可能大
所谓子串是指:在字符串中连续的一段
【输入】
输入文件为girl.in
输入有三行,第一行为一个字符串s1第二行为一个字符串s2, 
第三行为一个字符串s3。输入仅含小写字母,字符中间不含空格。
【输出】
输出文件为girl.out
输出仅有一行,为w的最大可能长度,如w不存在,则输出0。
【输入样例】
abcdef
abcf
bc
【输出样例】
2
【样例解释】
s1和s2的公共子串有abc,ab,bc,a,b,c,f,其中abc,bc包含子串bc不合法,所以最长的合法子串为ab。
【数据规模】
对于30%的数据:1<=s1、s2、s3的长度<=500
对于60%的数据:1<=s1、s2、s3的长度<=5000
对于100%的数据:1<=s1、s2的长度<=50000,1<=s3的长度<=10000


输入格式

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


输出格式

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


样例输入

abcdef
abcf
bc

样例输出

2
【样例解释】
s1和s2的公共子串有abc,ab,bc,a,b,c,f,其中abc,bc包含子串bc不合法,所以最长的合法子串为ab。

提示

对于100%的数据:1<=s1、s2的长度<=50000,1<=s3的长度<=10000


题目来源

没有写明来源