P83922

不同的公共子串

难度 6 级 动态规划入门 双序列
讨论 统计 9通过 17提交 52.9%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

输入

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

输出

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

样例

样例 1
输入
apartment
apache
输出
13

提示

公共子串有:"a"、"p"、"ap"、"pa"、"aa"、"apa"、"e"、"ae"、"pe"、"ape"、"pae"、"aae"、"apae"。 其中子串 "a"、"ae" 有多个,但由于统计的是公共子串种类,所以只算1种子串。

strlen(s) \leq 1000

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交