Show problems as
Classic problem #2851HardMathStringDynamic ProgrammingString Matching

String Transformation

Real-world version: Turning a Word Onto Its Target
Tracked in this browser only
Read String Transformation on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two words s and t have the same length n, which is at least 2, and hold only lowercase letters.

One turn on s works like this: pick a cut length c with 1 <= c <= n - 1, take the last c letters off the end of s, and put them back on at the front keeping their order. So s becomes the last c letters followed by the first n - c letters.

Two sequences of turns are counted apart when they pick a different cut length on some turn, even if the words they pass through are the same.

Return how many sequences of exactly k turns carry s to t, taken modulo 10^9 + 7.

Examples

Example 1

Input
s = "ab", t = "ba", k = 1
Output
1

With two letters the only allowed cut length is one, and taking the last letter to the front swaps the pair.

Example 2

Input
s = "abab", t = "abab", k = 2
Output
5

Each turn picks one of three cut lengths, so there are nine sequences of two turns. The word reads the same after sliding it two places as it does untouched, so a sequence lands on the target when its two cut lengths add to two, four or six: that is 1 with 1, 1 with 3, 2 with 2, 3 with 1, and 3 with 3.

Example 3

Input
s = "xyz", t = "zyx", k = 4
Output
0

Sliding letters round never reverses their order, so no slide turns the word into the target and no sequence of turns can either.

Constraints

  • 2 <= s.length <= 5 * 10^5
  • s.length == t.length
  • 1 <= k <= 10^15
  • s and t hold only lowercase English letters

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def number_of_ways(s: str, t: str, k: int) -> int:
Java
public int numberOfWays(String s, String t, long k)

More on the same topics