I was asked this question but couldn't manage to solve this, can someone please guide me, thanks!

Question

You are given two strings A and B that are made of lowercase English alphabets. Find the number of different pairs ((i, j), (k,l)) such that the substrings A[i...j] and B[k...l] are equal and the value of j - i + 1 is minimum.

Input Format

• The first line consists of a string denoting A.
• The second line consists f a string denoting B.

Output Format

Print the number of different pairs ((i, j), (k,l)) such that the substrings A[i...j] and B[k...l] are equal and the value of j-i+1 is minimum.

Constraints

1<=|A|, |B|<=10^5

Sample Input
abdc
bd

Sample Output
2

Explanation
Pairsa are ((1, 1), (0, 0)) and ((2, 2), (1, 1))