作者推荐
【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II
涉及知识点
LeetCode 2851. 字符串转换
给你两个长度都为 n 的字符串 s 和 t 。你可以对字符串 s 执行以下操作：
将 s 长度为 l （0 < l < n）的 后缀字符串 删除，并将它添加在 s 的开头。
比方说，s = ‘abcd’ ，那么一次操作中，你可以删除后缀 ‘cd’ ，并将它添加到 s 的开头，得到 s = ‘cdab’ 。
给你一个整数 k ，请你返回 恰好 k 次操作将 s 变为 t 的方案数。
由于答案可能很大，返回答案对 109 + 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 * 105
1 <= k <= 1015
s.length == t.length
s 和 t 都只包含小写英文字母。
矩阵快速幂
想到快速指数幂时，非常容易想到n阶方阵。n阶方阵自乘一次的时间复杂度就是O(n3)，严重超时。
可以优化到2阶方阵。
操作若干次后，假定s[0]的新下标为j。则s[j,n)+s[0,j) ≡ \equiv≡ s ，故若干操作后的状态，可以记为j。某次操作前状态为j1,操作后为j2，则j 2 ∈ [ 0 , j 1 ) ∪ ( j 1 , n ) 即除 j 1 外的所有值 j2\in[0,j1) \cup (j1,n) \quad \quad \quad \quad\quad 即除j1外的所有值j2∈[0,j1)∪(j1,n)即除j1外的所有值
性质一:j3 > 0 j4>0 操作若干次后，结果为j3和j4的可能数相等。
初始状态
pre[0]=1 其它为0 符合
前置状态符合pre[j3] == pre[j4]，操作一次后，后置状态符合dp[3]==dp[4]。
dp[j3] = ∑ m : 0 n − 1 \Large \sum_{m:0}^{n-1}∑m:0n−1pre(m) - pre[j3]
dp[j4] =∑ m : 0 n − 1 \Large \sum_{m:0}^{n-1}∑m:0n−1pre(m) - pre[j4]
dp[j3]-dp[j4] = pre[j3]-pre[j4] = 0。
动态规划的状态表示
只需要两种状态j为0，j不为0。
pre[0] = 1,pre[1]=0
动态规划的转移方程
dp[0] = pre[1](n-1)
dp[1] = pre[0] +pre[1](n-2)
超时
k的最大值是1012，大幅超时。用矩阵指数幂。
令矩阵是mat则
{ d p [ 0 ] = p r e [ 0 ] m a t [ 0 ] [ 0 ] + p r e [ 1 ] m a t [ 1 ] [ 0 ] d p [ 1 ] = p r e [ 0 ] m a t [ 0 ] [ 1 ] + p r e [ 1 ] m a t [ 1 ] [ 1 ] → [ 0 1 n − 1 n − 2 ] \begin{cases} dp[0] = pre[0]mat[0][0] + pre[1]mat[1][0] \\ dp[1] = pre[0]mat[0][1] + pre[1]mat[1][1] \\ \end{cases} \rightarrow\begin{bmatrix} 0 & 1 \\ n-1 & n-2 \\ \end{bmatrix}{dp[0]=pre[0]mat[0][0]+pre[1]mat[1][0]dp[1]=pre[0]mat[0][1]+pre[1]mat[1][1]→[0n−11n−2]
KMP
还需要判断s[j,n)和t[0,j-n) 和 s[0,j)和t[j-n,n) 是否相等。
代码
核心代码
class KMP { public: virtual int Find(const string& s, const string& t) { CalLen(t); m_vSameLen.assign(s.length(), 0); for (int i1 = 0, j = 0; i1 < s.length(); ) { for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++); //i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等 m_vSameLen[i1] = j; //t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2) if (0 == j) { i1++; continue; } const int i2 = i1 + j; j = m_vLen[j - 1]; i1 = i2 - j;//i2不变 } for (int i = 0; i < m_vSameLen.size(); i++) {//多余代码是为了增加可测试性 if (t.length() == m_vSameLen[i]) { return i; } } return -1; } vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性 static vector<int> Next(const string& s) { const int len = s.length(); vector<int> vNext(len, -1); for (int i = 1; i < len; i++) { int next = vNext[i - 1]; while ((-1 != next) && (s[next + 1] != s[i])) { next = vNext[next]; } vNext[i] = next + (s[next + 1] == s[i]); } return vNext; } protected: void CalLen(const string& str) { m_vLen.resize(str.length()); for (int i = 1; i < str.length(); i++) { int next = m_vLen[i - 1]; while (str[next] != str[i]) { if (0 == next) { break; } next = m_vLen[0]; } m_vLen[i] = next + (str[next] == str[i]); } } int m_c; vector<int> m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀 }; template<int MOD = 1000000007> class C1097Int { public: C1097Int(long long llData = 0) :m_iData(llData% MOD) { } C1097Int operator+(const C1097Int& o)const { return C1097Int(((long long)m_iData + o.m_iData) % MOD); } C1097Int& operator+=(const C1097Int& o) { m_iData = ((long long)m_iData + o.m_iData) % MOD; return *this; } C1097Int& operator-=(const C1097Int& o) { m_iData = (m_iData + MOD - o.m_iData) % MOD; return *this; } C1097Int operator-(const C1097Int& o) { return C1097Int((m_iData + MOD - o.m_iData) % MOD); } C1097Int operator*(const C1097Int& o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int& operator*=(const C1097Int& o) { m_iData = ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator<(const C1097Int& o)const { return m_iData < o.m_iData; } C1097Int pow(long long n)const { C1097Int iRet = 1, iCur = *this; while (n) { if (n & 1) { iRet *= iCur; } iCur *= iCur; n >>= 1; } return iRet; } C1097Int PowNegative1()const { return pow(MOD - 2); } int ToInt()const { return m_iData; } private: int m_iData = 0;; }; class CMat { public: // 矩阵乘法 static vector<vector<long long>> multiply(const vector<vector<long long>>& a, const vector<vector<long long>>& b) { const int r = a.size(), c = b.front().size(), iK = a.front().size(); assert(iK == b.size()); vector<vector<long long>> ret(r, vector<long long>(c)); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { for (int k = 0; k < iK; k++) { ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % s_llMod; } } } return ret; } // 矩阵快速幂 static vector<vector<long long>> pow(const vector<vector<long long>>& a, vector<vector<long long>> b, long long n) { vector<vector<long long>> res = a; for (; n; n /= 2) { if (n % 2) { res = multiply(res, b); } b = multiply(b, b); } return res; } static vector<vector<long long>> TotalRow(const vector<vector<long long>>& a) { vector<vector<long long>> b(a.front().size(), vector<long long>(1, 1)); return multiply(a, b); } protected: const static long long s_llMod = 1e9 + 7; }; class Solution { public: int numberOfWays(string s, string t, long long k) { const int n = s.length(); KMP kmp1,kmp2; kmp1.Find(t, s); kmp2.Find(s, t); vector<bool> vSame(n); for (int j = 0; j < n; j++) { if (kmp1.m_vSameLen[j] >= (n - j)) {// t[j,n) == s[0,n-j) if ((0==j)||(kmp2.m_vSameLen[n-j] >= j )) {//s[n-j,n) == t[0,j) vSame[j] = true; } } } vector<vector<long long >> mat = { {0,1},{n-1,n-2} }; vector<vector<long long >> pre = { {1,0} }; auto res = CMat::pow(pre, mat, k); C1097Int<> biRet; for (int i = 0; i < n; i++) { if (vSame[i]) { biRet += res[0][0 != i]; } } return biRet.ToInt(); } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string s,t; long long k = 0; { Solution sln; s = "abcd", t = "cdab", k = 2; auto res = sln.numberOfWays(s, t, k); Assert(res,2); } { Solution sln; s = "ababab", t = "ababab", k = 1; auto res = sln.numberOfWays(s, t, k); Assert(res, 2); } }
2023年9月
class KMP
{
public:
virtual int Find(const string& s,const string& t )
{
CalLen(t);
m_vSameLen.assign(s.length(), 0);
for (int i1 = 0, j = 0; i1 < s.length(); )
{
for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);
//i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等
m_vSameLen[i1] = j;
//t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2)
if (0 == j)
{
i1++;
continue;
}
const int i2 = i1 + j;
j = m_vLen[j - 1];
i1 = i2 - j;//i2不变
}
for (int i = 0; i < m_vSameLen.size(); i++) {//多余代码是为了增加可测试性 if (t.length() == m_vSameLen[i]) { return i; } } return -1; } vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性
protected:
void CalLen(const string& str)
{
m_vLen.resize(str.length());
for (int i = 1; i < str.length(); i++)
{
int next = m_vLen[i-1];
while (str[next] != str[i])
{
if (0 == next)
{
break;
}
next = m_vLen[0];
}
m_vLen[i] = next + (str[next] == str[i]);
}
}
int m_c;
vector m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀
};
class CMat
{
public:
// 矩阵乘法
static vector<vector> multiply(vector<vector>& a, vector<vector>& b) {
vector<vector> c(2, vector(2));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % s_llMod;
}
}
return c;
}
// 矩阵快速幂
static vector<vector> pow(vector<vector>& a, long long n) {
vector<vector> res = { {1, 0}, {0, 1} };
for (; n; n /= 2) {
if (n % 2) {
res = multiply(res, a);
}
a = multiply(a, a);
}
return res;
}
protected:
const static long long s_llMod = 1e9 + 7;
};
class Solution {
public:
int numberOfWays(string s, string t, long long k) {
int n = s.length();
KMP kmp1,kmp2;
kmp1.Find(s, t);
kmp2.Find(t, s);
int good = 0; //好下标的次数
for (int i = 0; i < n; i++)
{
const int leftLen = n - i;
if (kmp1.m_vSameLen[i] != leftLen)
{
continue;
}
const int rightLen = n - leftLen;
if ((0 == rightLen)|| (kmp2.m_vSameLen[n-rightLen] == rightLen ))
{
good++;
}
}
vector<vector> mat = { {good - 1,n-good},{good,n-good - 1} };
const int iGoodFirst = good - (s == t);//改变一次后，好下标的数量
vector<vector> vRes = { {iGoodFirst,n - iGoodFirst - 1},{0,0} };
k–;
auto matk = CMat::pow(mat,k);
vRes = CMat::multiply(vRes, matk);
return vRes[0][0];
}
};
