字符串转换

难度: Hard

给你两个长度都为 n 的字符串 s 和 t 。你可以对字符串 s 执行以下操作：

将 s 长度为 l （0 < l < n）的 后缀字符串 删除，并将它添加在 s 的开头。
比方说，s = 'abcd' ，那么一次操作中，你可以删除后缀 'cd' ，并将它添加到 s 的开头，得到 s = 'cdab' 。

给你一个整数 k ，请你返回恰好 k 次操作将 s 变为 t 的方案数。

由于答案可能很大，返回答案对 10⁹ + 7 取余后的结果。

示例 1：

输入：s = "abcd", t = "cdab", k = 2
输出：2
解释：
第一种方案：
第一次操作，选择 index = 3 开始的后缀，得到 s = "dabc" 。
第二次操作，选择 index = 3 开始的后缀，得到 s = "cdab" 。

第二种方案：
第一次操作，选择 index = 1 开始的后缀，得到 s = "bcda" 。
第二次操作，选择 index = 1 开始的后缀，得到 s = "cdab" 。

示例 2：

输入：s = "ababab", t = "ababab", k = 1
输出：2
解释：
第一种方案：
选择 index = 2 开始的后缀，得到 s = "ababab" 。

第二种方案：
选择 index = 4 开始的后缀，得到 s = "ababab" 。

提示：

2 <= s.length <= 5 * 10⁵
1 <= k <= 10¹⁵
s.length == t.length
s 和 t 都只包含小写英文字母。

Submission

运行时间: 72 ms

内存: 0.0 MB

class Solution:
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        n = len(s)
        ss = s + s
        first = ss.find(t)
        if first == -1:
            return 0
        elif first == 0:
            zero_targets = 1
        else:
            zero_targets = 0
        period = ss.find(s, 1)
        frequency = len(s) // period
        nonzero_targets = frequency - zero_targets
        MOD = 10 ** 9 + 7
        x = -1 if (k&1) == 1 else 1
        ways_0 = (pow(n - 1, k, MOD * n) + (n - 1) * x) // n
        ways_1 = (pow(n - 1, k, MOD * n) - x) // n
        return (zero_targets * ways_0 + nonzero_targets * ways_1) % MOD

Explain

本题解使用周期性和数学方法。首先，通过拼接字符串s到其自身来形成新的字符串ss，这样可以模拟任何后缀转移到前缀的操作。利用ss，算法首先查找目标字符串t在ss中的首次出现位置，如果未找到，直接返回0。如果找到，确定转移的周期性。周期性是通过在ss中查找s的起始位置1处的下一个s出现位置来确定。然后，根据周期和长度n计算在k次操作后，从首次出现位置可以转移到目标t的不同方式的数量。计算这些方式的数量涉及到使用pow函数来高效地计算大数的幂，并结合周期性和首次出现位置进行计算。最终，结合周期性出现的情况（是否从索引0开始）来计算恰好k次操作后达到目标的总方案数。

时间复杂度: O(n + log k)

空间复杂度: O(n)

# Python code for the solution with added comments

class Solution:
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        n = len(s)  # Length of the string
        ss = s + s  # Create double string to simulate rotations
        first = ss.find(t)  # Find first occurrence of t in ss
        if first == -1:  # t not found in ss
            return 0
        elif first == 0:  # Check if t starts at index 0
            zero_targets = 1
        else:
            zero_targets = 0
        period = ss.find(s, 1)  # Find the period of rotation
        frequency = len(s) // period  # Calculate frequency of rotation
        nonzero_targets = frequency - zero_targets
        MOD = 10 ** 9 + 7  # Modulus for large number operations
        x = -1 if (k & 1) == 1 else 1  # Determine parity of k
        ways_0 = (pow(n - 1, k, MOD * n) + (n - 1) * x) // n  # Calculate ways when starting at index 0
        ways_1 = (pow(n - 1, k, MOD * n) - x) // n  # Calculate ways for other starting indices
        return (zero_targets * ways_0 + nonzero_targets * ways_1) % MOD  # Return the total number of ways modulo MOD

Explore

当字符串s拼接成ss后，可以通过ss模拟s的任意循环位移。周期性是指s的循环重复的最小单位长度。首次出现位置是指t在ss中第一次出现的位置。如果t在ss中首次出现的位置与s的周期性位置对应，这意味着t可以通过周期性位移从s的开始位置匹配。例如，如果周期性为s的长度，那么每次完整的s的位移都可能重新匹配到t，从而形成周期性行为。

从ss的索引1开始搜索s的下一个出现位置是为了找到s可能的最小周期性。即寻找s不是完整出现在ss开头时的最早出现点。如果s在ss中以不同的方式重叠，例如部分重叠，那么这种重叠会影响实际的周期性。通过从索引1开始搜索，可以确保我们找到的是除完全重叠外的最小周期。

计算k次操作后从首次出现的位置转移到目标t的方式，涉及到使用幂运算来模拟周期性位移的影响。使用pow函数计算`(n-1)^k`，其中n是s的长度。这代表所有可能的位移组合。然后，根据首次出现的位置是0还是非0，使用不同的计算公式来确定确切的转移方式数量。如果首次出现位置为0，计算方式稍有不同，因为从索引0开始的转移和其他位置的转移在周期性上可能有所不同。

在计算方式数量时，使用MOD * n主要是为了防止大数溢出并进行模运算以简化计算。MOD通常是一个大的质数，如10^9+7，用于取余保证结果的范围内有效性。乘以n是为了在取模操作中保持精度，确保在整个计算过程中不会因为过大的数字而失去精度或引发计算错误。