1093HardMathStringDynamic ProgrammingString Matching

Turning a Word Onto Its Target

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def number_of_ways(s: str, t: str, k: int) -> int:

Java

public int numberOfWays(String s, String t, long k)

The intended approach

Time O(n + log k) for the prefix-function pass and the power.Space O(n) for the doubled word and the prefix function.

A turn with cut length `c` slides every letter `c` places to the right and wraps the overflow around. Two turns in a row slide by the sum of their cut lengths, so a whole sequence of `k` turns is settled by the sum of its cut lengths taken modulo `n`. Nothing else about the sequence matters. That splits the job in two: which total slides land on `t`, and how many sequences of `k` cut lengths reach a given total. For the first half, a slide of `m` turns `s` into the piece of `s` starting at position `n - m` read round the end. Every one of those is a window of length `n` inside `s` written twice, so a single prefix-function pass over `t`, a separator and the first `2n - 1` letters of the doubled word finds all of them at once. A window starting at position zero is the slide that goes nowhere, the rest are non-zero slides. For the second half, let `A` count the sequences of `k` cut lengths that sum to zero modulo `n` and `B` count those summing to one fixed non-zero value. By symmetry every non-zero value has the same count, so `A + (n - 1)B` is `(n - 1)^k`. Peeling off the last turn gives `A = (n - 1)B'` and `B = A' + (n - 2)B'` on the previous length, and those two settle into `B = ((n - 1)^k - (-1)^k) / n` and `A = ((n - 1)^k + (n - 1)(-1)^k) / n`. Both divisions are exact, and modulo a prime they are done with the inverse of `n`. Multiply `A` by whether the do-nothing slide lands on `t`, add `B` times the number of non-zero slides that do, and that is the answer.

Pythonentry point: number_of_ways

def number_of_ways(s, t, k):
    mod = 1000000007
    n = len(s)
    total = pow(n - 1, k, mod)
    sign = 1 if k % 2 == 0 else mod - 1
    inv = pow(n % mod, mod - 2, mod)
    stay = (total + (n - 1) % mod * sign) % mod * inv % mod
    move = (total - sign) % mod * inv % mod
    doubled = s + s
    pattern = t + "\x00" + doubled[:2 * n - 1]
    fail = [0] * len(pattern)
    for i in range(1, len(pattern)):
        j = fail[i - 1]
        while j and pattern[i] != pattern[j]:
            j = fail[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        fail[i] = j
    stay_hits = 0
    move_hits = 0
    for i in range(len(pattern)):
        if fail[i] == n:
            if i - 2 * n == 0:
                stay_hits += 1
            else:
                move_hits += 1
    return (stay_hits * stay + move_hits * move) % mod

The obvious version

Spell out every sequence of cut lengths, one choice from one to `n - 1` per turn, apply the turns to `s` one after another and count the sequences whose final word is `t`. Costs `n - 1` to the power of `k`, so only tiny words and turn counts survive.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_number_of_ways(s, t, k):
    from itertools import product
    mod = 1000000007
    n = len(s)
    hits = 0
    for choice in product(range(1, n), repeat=k):
        cur = s
        for c in choice:
            cur = cur[n - c:] + cur[:n - c]
        if cur == t:
            hits += 1
    return hits % mod

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in