← 返回题目列表

Codeforces · 1090/J

J. 两个前缀

中文机器翻译题面 查看原题

Misha 再次没有做今天课的数学作业。作为惩罚,他的老师安德鲁博士决定给他一项艰巨但非常无用的任务。

安德鲁博士写了两个字符串 黑板上的 s 和 t 小写英文字母。他提醒米莎 前缀 字符串的 是通过删除其最后几个字符(可能没有)而形成的字符串,并且 串联 两个字符串的 是通过将第二个字符串附加到第一个字符串的右侧而形成的字符串。

老师要求 Misha 在黑板上写下所有由以下非空前缀串联而成的字符串 s 和一些非空前缀 t。当米沙这样做时,安德鲁博士问他有多少条不同的绳子。米莎几乎用了整个课程的时间来完成这个任务并完成了任务。

现在他要求你编写一个程序来自动执行此任务。

输入

第一行包含字符串 s 由小写英文字母组成。第二行包含字符串 t 由小写英文字母组成。

两个字符串的长度不超过 105.

输出

输出一个整数 - 由某些非空前缀串联而成的不同字符串的数量 s 带有一些非空前缀 t.

示例

输入
复制

aba
aa

输出
复制

5

输入
复制

aaaaa
aaaa

输出
复制

8

注意

在第一个示例中,字符串 s 有三个非空前缀:{a, ab, 阿巴}。字符串 t 有两个非空前缀:{a, aa}。 Misha 总共写了五个不同的字符串:{aa, aaa, 阿巴, abaa, 啊啊啊}。字符串 abaa 已被写入两次。

在第二个示例中,Misha 编写了八个不同的字符串:{aa, aaa, 啊啊啊, 啊啊啊, 啊啊啊啊, 啊啊啊啊啊, 啊啊啊啊啊啊, 啊啊啊啊啊啊}.