P99270

公共子串种类数

难度 6 级动态规划入门双序列

讨论统计 18通过 57提交 31.6%通过率旧版界面

时间限制 1 秒 内存限制 128 MB

题目描述

在一个字符串中，子串是在字符串的基础上去掉0个或若干个字符后所形成的字符串，现有字符串 $"aabbcc"$ 其中 $"abc"$ 、 $"aa"$ 、 $"abbc"$ 、 $"bbcc"$ 等都是它的子串，现在给出个字符串，找出3个字符串共同含有多少种子串（不算空串），在公共子串中出现位置不同，只算一种。

输入

每组数据只含3行，每行都是只包含小写字母的字符串。

输出

输出3个字符串共有的公共子串种类数。

样例

样例 1

输入

apartment
apache
approach

输出

提示

3个字符串共有的公共子串有： $"a"$ 、 $"p"$ 、 $"ap"$ 、 $"pa"$ 、 $"aa"$ 、 $"apa"$ 。其中子串 $"a"$ 有多个，但由于统计的是公共子串种类，所以只算1种子串。

$strlen(s) \leq 200$

来源

云南编程挑战赛

上一题下一题