String transformation

Math String Dynamic Programming String Matching

26.8% acceptance

Feb 25, 2026

183

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_ways(s: String, t: String, k: i64) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = s.len();
    let ss = s.as_bytes();
    let tt = t.as_bytes();

    // KMP: count occurrences of pattern in text at rotation-start positions in [include_zero ? 0 : 1, n)
    let kmp_count = |text: &[u8], pattern: &[u8], include_zero: bool| -> i64 {
      let m = pattern.len();
      let mut fail = vec![0usize; m];
      let mut j = 0usize;
      for i in 1..m {
        while j > 0 && pattern[j] != pattern[i] { j = fail[j-1]; }
        if pattern[j] == pattern[i] { j += 1; }
        fail[i] = j;
      }
      let mut count = 0i64;
      j = 0;
      for i in 0..text.len() {
        while j > 0 && pattern[j] != text[i] { j = fail[j-1]; }
        if pattern[j] == text[i] { j += 1; }
        if j == m {
          let start = i + 1 - m;
          if (include_zero || start > 0) && start < n { count += 1; }
          j = fail[j-1];
        }
      }
      count
    };

    // p = number of rotations of s (positions 0..n-1) that give t
    // (from any non-t state r, rotating by l covers all positions except r,
    //  including position 0, so include_zero = true)
    let text_st: Vec<u8> = ss.iter().chain(ss.iter()).cloned().collect();
    let p = kmp_count(&text_st, tt, true);

    // q = number of rotations of t (positions 1..n-1) that give t (transitions from t to t)
    let text_tt: Vec<u8> = tt.iter().chain(tt.iter()).cloned().collect();
    let q = kmp_count(&text_tt, tt, false);

    let n1 = n as i64 - 1;
    // Matrix: M[i][j] = transitions from state j to state i
    // states: 0 = at t, 1 = not at t
    // M = [[q, p], [n1-q, n1-p]]
    let mat_mul = |a: &[[i64;2];2], b: &[[i64;2];2]| -> [[i64;2];2] {
      let mut c = [[0i64;2];2];
      for i in 0..2 { for j in 0..2 { for l in 0..2 {
        c[i][j] = (c[i][j] + a[i][l] * b[l][j]) % MOD;
      }}}
      c
    };
    let mat_pow = |mut m: [[i64;2];2], mut exp: i64| -> [[i64;2];2] {
      let mut result = [[1i64,0],[0,1i64]];
      while exp > 0 {
        if exp & 1 == 1 { result = mat_mul(&result, &m); }
        m = mat_mul(&m, &m);
        exp >>= 1;
      }
      result
    };
    let mat = [
      [q % MOD, p % MOD],
      [(n1 - q % MOD + MOD) % MOD, (n1 - p % MOD + MOD) % MOD],
    ];
    let result = mat_pow(mat, k);
    let is_same = ss == tt;
    // result[0][0] * a_init + result[0][1] * b_init
    let ans = if is_same {
      result[0][0] // [1, 0]
    } else {
      result[0][1] // [0, 1]
    };
    (ans % MOD) as i32
  }
}