String Shift Transformation :
Difficulty Level : Hard
Submissions : 140
Asked In :
Marks :10
: 4 | : 0
Given two strings $$$src$$$ and $$$target$$$, and an integer $$$k$$$.
In one operation you can remove the suffix of any length from the $$$src$$$ string and add it to the front of the remaining string.
You have to tell the number of ways to transform $$$src$$$ string to $$$target$$$ string in exactly $$$k$$$ operations modulo $$$10^9+7$$$.
The first line contains a string $$$src, (2 \le |src| \le 1000)$$$
The second line contains a string $$$target, (2 \le |target| \le 1000)$$$
The third line contains an integer $$$k, ( 1 \le k \le 10^6)$$$
Print the number of ways to transform $$$src$$$ to $$$target$$$ in exactly $$$k$$$ operations modulo $$$10^9+7$$$.
abcd cdab 2
2
ababab ababab 1
2
In the given example, there are following ways:
- "abcd" can be transformed to "bcda" by selecting suffix "bcd" and "bcda" can be transformed to "cdab" by selecting the suffix "cda"
- "abcd" can be transformed to "dabc" by selecting "d" and "dabc" can be transformed to "cdab" by selecting suffix "c".
So, there are 2 ways to transform in exactly $$$k$$$ steps. Hence, the answer is 2.
