7796: BZOJ3796：Mushroom追妹纸

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

题目来源

没有写明来源