字符串转换

You are given two strings s and t of equal length n. You can perform the following operation on the string s:

• Remove a suffix of s of length l where 0 < l < n and append it at the start of s.
  For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.

You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.

Since the answer can be large, return it modulo 109 + 7.

 

Example 1:

Input: s = "abcd", t = "cdab", k = 2
Output: 2
Explanation: 
First way:
In first operation, choose suffix from index = 3, so resulting s = "dabc".
In second operation, choose suffix from index = 3, so resulting s = "cdab".

Second way:
In first operation, choose suffix from index = 1, so resulting s = "bcda".
In second operation, choose suffix from index = 1, so resulting s = "cdab".

Example 2:

Input: s = "ababab", t = "ababab", k = 1
Output: 2
Explanation: 
First way:
Choose suffix from index = 2, so resulting s = "ababab".

Second way:
Choose suffix from index = 4, so resulting s = "ababab".

 

Constraints:

• 2 <= s.length <= 5 * 105
• 1 <= k <= 1015
• s.length == t.length
• s and t consist of only lowercase English alphabets.

/*
 * 思路：
 * 使用Java Stream处理类似思路，通过k次旋转操作将s变为t的方法数量可以通过使用最大公约数(gcd)来计算。
 * 首先，找到可以使s变为t的旋转索引，然后根据这些索引来判断经过k次操作后可以变为t的情况。
 * 我们需要考虑gcd的使用，因为在k次操作中可能会重复到某个状态。
 */
import java.util.*;
import java.util.stream.*;

public class SolutionStream {
    private static final int MOD = 1000000007;

    public int numberOfWays(String s, String t, long k) {
        int n = s.length();
        List<Integer> validShifts = IntStream.range(0, n)
            .filter(i -> (s.substring(i) + s.substring(0, i)).equals(t))
            .boxed()
            .collect(Collectors.toList());

        long gcd = gcd(k, n);
        long cycles = k / gcd;
        long count = validShifts.stream()
            .filter(shift -> shift % gcd == 0)
            .count();

        return (int) ((count * cycles) % MOD);
    }

    private long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        SolutionStream solution = new SolutionStream();
        System.out.println(solution.numberOfWays("abcd", "cdab", 2)); // 输出: 2
        System.out.println(solution.numberOfWays("ababab", "ababab", 1)); // 输出: 2
    }
}

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

O(n + log k)

O(n)