重庆网站建设找承越,免费建设个人网站,郑州楼市最新消息,进出口贸易网作者推荐
【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II
涉及知识点
【矩阵快速幂】封装类及测试用例及样例
LeetCode 2851. 字符串转换
给你两个长度都为 n 的字符串 s 和 t 。你可以对字符串 s 执行以下操作#xff1a; 将 s 长度为 l #xff08;0 …作者推荐
【深度优先搜索】【树】【有向图】【推荐】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 j40 操作若干次后结果为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为0j不为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;}vectorint m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀增加可调试性static vectorint Next(const string s){const int len s.length();vectorint 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;vectorint m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀
};templateint 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 vectorvectorlong long multiply(const vectorvectorlong long a, const vectorvectorlong long b) {const int r a.size(), c b.front().size(), iK a.front().size();assert(iK b.size());vectorvectorlong long ret(r, vectorlong 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 vectorvectorlong long pow(const vectorvectorlong long a, vectorvectorlong long b, long long n) {vectorvectorlong long res a;for (; n; n / 2) {if (n % 2) {res multiply(res, b);}b multiply(b, b);}return res;}static vectorvectorlong long TotalRow(const vectorvectorlong long a){vectorvectorlong long b(a.front().size(), vectorlong 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);vectorbool vSame(n);for (int j 0; j n; j){if (kmp1.m_vSameLen[j] (n - j)){// t[j,n) s[0,n-j)if ((0j)||(kmp2.m_vSameLen[n-j] j )){//s[n-j,n) t[0,j)vSame[j] true;}}}vectorvectorlong long mat { {0,1},{n-1,n-2} };vectorvectorlong 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();}
};测试用例
templateclass T,class T2
void Assert(const T t1, const T2 t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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;
}
vectorint 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 vectorvector multiply(vectorvector a, vectorvector b) { vectorvector 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 vectorvector pow(vectorvector a, long long n) { vectorvector 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; } } vectorvector mat { {good - 1,n-good},{good,n-good - 1} }; const int iGoodFirst good - (s t);//改变一次后好下标的数量 vectorvector vRes { {iGoodFirst,n - iGoodFirst - 1},{0,0} }; k–; auto matk CMat::pow(mat,k); vRes CMat::multiply(vRes, matk); return vRes[0][0]; } };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
