Marks :20
: 3 | : 2
Given two non-empty strings $$$s$$$ and $$$t$$$, consisting of lowercase Latin letters. Your task is to calculate the number of different pairs of $$$\textbf{(a b)}$$$ such that $$$a$$$ is a substring of string $$$s$$$, $$$b$$$ is a subsequence of string $$$t$$$, and the content of $$$a$$$ and $$$b$$$ is the same. Two pairs are considered different, if they contain different substrings of string $$$s$$$ or different subsequences of string $$$t$$$.
A substring of $$$s$$$ is a non-empty string $$$x = s[a... b] = s_as_{a + 1}... s_b (1 \le a \le b \le |s|)$$$. Two substrings $$$s[a... b]$$$ and $$$s[c... d]$$$ are considered to be different if $$$a ≠ c$$$ or $$$b ≠ d.$$$
A subsequence of $$$s$$$ is a non-empty string $$$y = s[p_1p_2... p_{|y|}] = s_{p_1}s_{p_2}... s_{p_{|y|}} (1 \le p_1 \lt p_2 \lt ... \lt p_{|y|} \le |s|)$$$. Two subsequences $$$u = s[p_1p_2... p_{|u|}]$$$ and $$$v = s[q_1q_2... q_{|v|}]$$$ are considered different if the sequences $$$p$$$ and $$$q$$$ are different.
The input consists of two lines. The first of them contains $$$s$$$ $$$(1 \le |s| \le 1000)$$$, and the second one contains $$$t$$$ $$$(1 \le |t| \le 1000)$$$. Both strings consist of lowercase Latin letters.
Print a single number — the number of different pairs of $$$\textbf{(a b)}$$$ such that $$$a$$$ is a substring of string $$$s$$$, $$$b$$$ is a subsequence of string $$$t$$$, and the content of $$$a$$$ and $$$b$$$ is the same. As the answer can be rather large, print it modulo $$$1000000007 (10^9 + 7)$$$.
aa aa
5
In the sample testcase, following are the valid $$$\textbf{(a b)}$$$ pairs:
You need to login to view your submissions.
You need to login to view all submissions.
Result : Executed
Feel something is wrong with the test cases?
Result : Accepted
Test Cases :
But to Run or Submit the Problem, you need to Log In.
Continue to Log InYour challenge has been submitted successfully.
You will get a response soon via WhatsApp or Email.
Do let us know your issue.