Problem6421--[HAOI2016]找相同子串

6421: [HAOI2016]找相同子串

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

Input

两行,两个字符串 $s_1,s_2$。

Output

输出一个整数表示答案。

Constraints

对于 $20\%$ 的数据,满足 $1≤n_1,n_2≤500$;
对于 $40\%$ 的数据,满足 $1≤n_1,n_2≤5,000$;
对于 $100\%$ 的数据,满足 $1≤n_1,n_2≤200,000$,字符串中只有小写字母。

Sample 1 Input

aabb
bbaa

Sample 1 Output

10

HINT

类似题目:POJ 3415

Source/Category