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 scan be transformed into t in exactlyk operations.
Since the answer can be large, return it modulo109 + 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.
"""DP, Z-algorithm, Fast mod.ApproachHow to represent a string?Each operation is just a rotation. Each result string can be represented by an integer from 0 to n - 1. Namely, it's just the new index of s[0].How to find the integer(s) that can represent string t?Create a new string s + t + t (length = 3 * n).Use Z-algorithm (or KMP), for each n <= index < 2 * n, calculate the maximum prefix length that each substring starts from index can match, if the length >= n, then (index - n) is a valid integer representation.How to get the result?It's a very obvious DP.If we use an integer to represent a string, we only need to consider the transition from zero to non-zero and from non-zero to zero. In other words, all the non-zero strings should have the same result.So let dp[t][i = 0/1] be the number of ways to get the zero/nonzero stringafter excatly t steps.Thendp[t][0] = dp[t - 1][1] * (n - 1).All the non zero strings can make it.dp[t][1] = dp[t - 1][0] + dp[t - 1] * (n - 2).For a particular non zero string, all the other non zero strings and zero string can make it.We have dp[0][0] = 1 and dp[0][1] = 0Use matrix multiplication.How to calculate dp[k][x = 0, 1] faster?Use matrix multiplicationvector (dp[t - 1][0], dp[t - 1][1])multiplies matrix[0 1][n - 1 n - 2]== vector (dp[t][0], dp[t - 1][1]).So we just need to calculate the kth power of the matrix which can be done by fast power algorith.ComplexityTime complexity:O(n + logk)Space complexity:O(n)"""classSolution:M:int=1000000007defadd(self,x:int,y:int)->int:x+=yifx>=self.M:x-=self.Mreturnxdefmul(self,x:int,y:int)->int:returnint(x*y%self.M)defgetZ(self,s:str)->List[int]:n=len(s)z=[0]*nleft=right=0foriinrange(1,n):ifi<=rightandz[i-left]<=right-i:z[i]=z[i-left]else:z_i=max(0,right-i+1)whilei+z_i<nands[i+z_i]==s[z_i]:z_i+=1z[i]=z_iifi+z[i]-1>right:left=iright=i+z[i]-1returnzdefmatrixMultiply(self,a:List[List[int]],b:List[List[int]])->List[List[int]]:m=len(a)n=len(a[0])p=len(b[0])r=[[0]*pfor_inrange(m)]foriinrange(m):forjinrange(p):forkinrange(n):r[i][j]=self.add(r[i][j],self.mul(a[i][k],b[k][j]))returnrdefmatrixPower(self,a:List[List[int]],y:int)->List[List[int]]:n=len(a)r=[[0]*nfor_inrange(n)]foriinrange(n):r[i][i]=1x=[a[i][:]foriinrange(n)]whiley>0:ify&1:r=self.matrixMultiply(r,x)x=self.matrixMultiply(x,x)y>>=1returnrdefnumberOfWays(self,s:str,t:str,k:int)->int:n=len(s)dp=self.matrixPower([[0,1],[n-1,n-2]],k)[0]s+=t+tz=self.getZ(s)m=n+nresult=0foriinrange(n,m):ifz[i]>=n:result=self.add(result,dp[0]ifi-n==0elsedp[1])returnresult