Smallest Common Substring :
Difficulty Level : Easy
Submissions : 281
Asked In :
Marks :10
: 1 | : 0
You are given two strings $$$s$$$ and $$$t$$$ consisting of lowercase Latin letters. Find the number of different pairs $$$((i,j), \hspace{1pt} (k,l))$$$ such that the substrings $$$s[i:j]$$$ and $$$t[k:l]$$$ are equal and the value of $$$j-i+1$$$ is minimum.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains two space separated integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 10^5)$$$ — the lengths of strings $$$s$$$ and $$$t$$$ respectively.
The second line of each testcase contains the string $$$s$$$ containing $$$n$$$ lowercase latin letters.
The third line of each testcase contains the string $$$t$$$ containing $$$m$$$ lowercase latin letters.
It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all testcases does not exceed $$$10^5$$$.
For each testcase, print the answer to the problem in a single line.
14 2abdcbd
2
In sample test case 1, Consider $$$s$$$ = "abdc" and $$$t$$$ = "bd". You must determine the answer such that it meets the given conditions:
- Let us choose a substring of length $$$1$$$, those are "b" and "d". The count is $$$2$$$.
- Let us choose a substring of length $$$2$$$, which is "bd". The count is $$$1$$$.
