【动态规划】【矩阵快速幂】LeetCode2851. 字符串转换

作者推荐

【深度优先搜索】【树】【有向图】【推荐】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−1​pre(m) - pre[j3]
dp[j4] = ∑ m : 0 n − 1 \Large \sum_{m:0}^{n-1} ∑m:0n−1​pre(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−1​1n−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];
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/399707.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

安达发|APS排产软件的机台产线任务甘特图功能详解

安达发|APS排产软件的机台产线任务甘特图功能详解

在现代制造业中&#xff0c;高级计划与排产是制造业运营的关键环节。为了提高生产效率、降低成本并确保产品质量&#xff0c;企业需要对生产过程进行精细化管理。APS&#xff08;高级计划与排产&#xff09;系统作为一种先进的生产计划和调度工具&#xff0c;可以帮助企业实现这…
阅读更多...
在计算机上设置和使用 KVM

在计算机上设置和使用 KVM

为了使用 gem5 的 KVMCPU 来快进你的模拟&#xff0c;你必须有一个 KVM 兼容的处理器并且在你的机器上安装了 KVM。本页将引导您完成在计算机上启用 KVM 并将其与 gem5 一起使用的过程。 注意&#xff1a;以下教程假设 X86 Linux 主机。本教程的各个部分可能不适用于其他体系结…
阅读更多...
IBM V5000存储更换控制器及电源模块

IBM V5000存储更换控制器及电源模块

LED故障状态 后面板故障状态 系统内电源模块报错信息(可安全卸下状态为"是"&#xff0c;此时可直接热拔插) 控制器报错信息&#xff08;当前已是脱机状态可直接拔插&#xff0c;该型号控制器不需要更换缓存可直接热拔插更换&#xff09; 更换故障备件应先核对新旧备件…
阅读更多...
CTFHub技能树web之RCE（二）

CTFHub技能树web之RCE（二）

第五题&#xff1a;远程包含 根据题目&#xff0c;使用远程包含进行 打开phpinfo&#xff0c;可以看到allow_url_fopen和allow_url_include都是On&#xff0c;因此可以使用php://input&#xff0c;由于代码会检查file中的内容&#xff0c;因此不能够使用php://filter包含文件&a…
阅读更多...
C++正则表达式笔记

C++正则表达式笔记

最近翻了翻正则表达式的一些资料&#xff0c;做个记录。 1、微软官方 <regex> 函数 | Microsoft Learn 2、正则表达式语法简介 正则表达式语法简介 - 简书 3、正则表达式基础语法大全 正则表达式基础语法大全_正则表达式语法大全-CSDN博客 4、练习 &#xff08;1…
阅读更多...
ffmpeg TS复用代码详解——mpegtsenc.c

ffmpeg TS复用代码详解——mpegtsenc.c

一、mpegtsenc.c 整体架构 二、主要函数 mpegts_write_pes(AVFormatContext *s, AVStream *st, const uint8_t *payload, int payload_size, int64_t pts, int64_t dts)这个函数就是TS打包的主函数了&#xff0c;这个函数主要功能就是把一帧数据拆分成188字节的TS包&#xff0…
阅读更多...
openai DALL-E 3 从文本描述生成图像原理通俗解释

openai DALL-E 3 从文本描述生成图像原理通俗解释

序言 在数字时代&#xff0c;图像生成技术正日益成为人工智能领域的热点。 本讨论将重点聚焦于两个备受瞩目的模型&#xff1a;DALL-E和其他主流AI绘图方法。 我们将探讨它们的优势、局限性以及未来的发展方向。通过比较分析&#xff0c;我们期望能够更全面地了解这些技术&a…
阅读更多...
Datawhale零基础入门金融风控Task1 赛题理解

Datawhale零基础入门金融风控Task1 赛题理解

Task1 赛题理解 Tip:本次新人赛是Datawhale与天池联合发起的0基础入门系列赛事第四场 —— 零基础入门金融风控之贷款违约预测挑战赛。 赛题以金融风控中的个人信贷为背景&#xff0c;要求选手根据贷款申请人的数据信息预测其是否有违约的可能&#xff0c;以此判断是否通过此项…
阅读更多...
jenkins的nmp install命令无法下载包

jenkins的nmp install命令无法下载包

问题&#xff1a;在jenkin的流水线脚本中执行到&#xff1a;npm install命令后无法下载前端依赖包 1、进到jenkins的工作目录&#xff0c;一般在底层为/var/lib/jenkins/workspace/任务名称 cd /var/lib/jenkins/workspace/xkc处理方式&#xff1a; # 查看镜像源 npm config …
阅读更多...
​【C语言】长篇详解，字符系列篇3-----strstr，strtok，strerror字符串函数的使用【图文详解​】

​【C语言】长篇详解，字符系列篇3-----strstr，strtok，strerror字符串函数的使用【图文详解​】

欢迎来CILMY23的博客喔&#xff0c;本期系列为​【C语言】长篇详解&#xff0c;字符系列篇3-----strstr&#xff0c;strtok&#xff0c;strerror字符串函数的使用【图文详解​】&#xff0c;图文讲解各种字符串函数&#xff0c;带大家更深刻理解C语言中各种字符串函数的应用&am…
阅读更多...
日常的一些异常

日常的一些异常

Column ‘id’ in where clause is ambiguous 这个错误in where clause is ambiguous多半是因为多表查询的时候几个表中同时出现了某个相同的列名&#xff0c;而在查询条件WHERE后面又没有指定是那个表&#xff0c;而引起的,又或者是查询结果里面有两个相同的列名&#xff0c;…
阅读更多...
[notice] A new release of pip is available: 23.2.1 -＞ 24.0

[notice] A new release of pip is available: 23.2.1 -＞ 24.0

翻译之后&#xff1a;〔通知〕新版本的pip可用&#xff1a;23.2.1->24.0 就是说&#xff0c;你的pip版本需要从当前的 23.2.1 升级到最新版本 24.0&#xff0c;执行如下命令&#xff1a; cmd命令以管理员身份进入目录 ${Python}\Python3.12.1\Scripts下&#xff0c;执行 p…
阅读更多...
好用便签：如何利用备忘录高效处理待办事项？

好用便签：如何利用备忘录高效处理待办事项？

在快节奏的现代生活中&#xff0c;我们需要处理各种各样的待办事项&#xff0c;从个人生活琐事到工作任务。如何利用备忘录高效处理待办事项&#xff0c;成为了提升效率和生活质量的关键。一个合理的待办事项规划不仅能帮助我们明确目标&#xff0c;还能让我们更加有条不紊地应…
阅读更多...
【软考高项】【教材知识梳理】- 17 - 第17章 - 项目干系人管理

【软考高项】【教材知识梳理】- 17 - 第17章 - 项目干系人管理

一、基本问题 问题1&#xff1a;干系人登记册包括什么? a.身份信息&#xff1a;姓名、 组织职位、 地点、 联系方式&#xff0c; 以及在项目中扮演的角色。b.评估信息&#xff1a;主要需求、 期望、 影响项目成果的潜力&#xff0c; 以及干系人最能影响或冲击的项目生命周期阶…
阅读更多...
知识付费App开发：重塑学习与知识的价值链

知识付费App开发：重塑学习与知识的价值链

随着互联网的普及和信息爆炸的时代&#xff0c;人们对于知识的渴求从未如此强烈。然而&#xff0c;如何在海量的信息中筛选出有价值的内容&#xff0c;成为了摆在用户面前的一大难题。此时&#xff0c;知识付费App应运而生&#xff0c;为用户提供了一个高效、便捷的知识获取与交…
阅读更多...
vscode 点击import引用的组件直接跳转方法

vscode 点击import引用的组件直接跳转方法

vs code。下载插件。 搜索名称&#xff1a;别名路径跳转
阅读更多...
小程序--自定义组件

小程序--自定义组件

一、创建自定义组件 .js中注册Component函数 .json使用"component": true Component({}) {"component": true } 二、使用自定义组件 全局配置、页面配置均可&#xff0c;全局配置就写在app.json中&#xff0c;页面配置就写在页面对应的json中。 配置之后…
阅读更多...
ncnn之三（补充）：window环境下vs2022安装ncnn+protobuf

ncnn之三（补充）：window环境下vs2022安装ncnn+protobuf

启动VS2022 下面的 x64 Native Tools Command Prompt for VS2022 protobuf git clone gitgithub.com:protocolbuffers/protobuf.git# 或者 下载 https://github.com/google/protobuf/archive/v3.11.2.zip cmake -G"NMake Makefiles" -DCMAKE_BUILD_TYPERelease -D…
阅读更多...
node+vue3+mysql前后分离开发范式——实现视频文件上传并渲染

node+vue3+mysql前后分离开发范式——实现视频文件上传并渲染

文章目录 ⭐前言⭐ 功能设计与实现💖 node上传文件写入file_map映射表💖 vue3前端上传文件回显⭐ 效果⭐结束⭐前言 大家好，我是yma16，本文分享关于 node+vue3+mysql前后分离开发范式——实现视频文件上传并渲染。 技术选型 前端：vite+vue3+antd 后端：node koa 数据库…
阅读更多...
如何实现系统的高可用

如何实现系统的高可用

一、SLA 当回答系统高可用时&#xff0c;就是回答这几个问题&#xff1a; 1、如何 评估系统高可用&#xff1f; 2、如何监控系统高可用&#xff1f; 3、如何保证系统高可用&#xff1f; 监控系统的内容&#xff1a; 基础设施监控有监控报警指标&#xff0c;分两部分内容&am…
阅读更多...
最新文章

Copyright @ 2022~2023