BZOJ 1009 HNOI2008 GT考试 KMP算法+矩阵乘法

简介:
标题效果:给定的长度m数字字符串s。求不包括子s长度n数字串的数目
n<=10^9 看这个O(n)它与
我们不认为这 令f[i][j]长度i号码的最后的字符串j位和s前者j数字匹配方案
例如,当s至12312时间 f[i][3]它表示的长度i。123结尾且不包括子串”12312“的方案数
a[x][y]为f[i-1][x]转移至f[i][y]的方案数
换句话说(可能描写叙述不清楚) a[x][y]为s的长度为x的前缀加上一个数字后 后缀能够与最长长度为y的前缀匹配 这个数字能够有多少种
比方说12312 这个数字串生成的a数组为(数组从0開始):
9 1 0 0 0 0
8 1 1 0 0 0
8 1 0 1 0 0
9 0 0 0 1 0
8 1 0 0 0 1
a[2][1]=1 表示长度为2的前缀加上一个'1'之后最多与长度为1的前缀匹配
a[4][0]=8 表示长度为4的前缀加上'1''2'以外的数就变成了长度为0的前缀
可是a[x][5]表示全然匹配,不满足要求的题意,所以我们矩阵乘法时不考虑这一列
我们发现f[i-1]乘上这个矩阵就变成了f[i] 这个矩阵怎么求呢?KMP算法,对于每一个长度的前缀枚举下一个字符进行转移 详细写法详见代码
f初值是f[0][0]=1,f[0][x]=0 (x>0)
于是最后我们仅仅须要取答案矩阵的第一行就可以

去网上找了一堆题解才看懂0.0 这里写的略微具体一点吧

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct matrix{
	int xx[22][22];
	int* operator [] (int x)
	{
		return xx[x];
	}
}a,b;
int n,m,p,ans;
char s[100];
int next[100];
void operator *= (matrix &x,matrix &y)
{
	int i,j,k;
	matrix z;
	memset(&z,0,sizeof z);
	for(i=0;i<m;i++)
		for(j=0;j<m;j++)
			for(k=0;k<m;k++)
				z[i][j]+=x[i][k]*y[k][j],z[i][j]%=p;
	x=z;
}
void KMP()
{
	int i,fix=0;
	char j;
	for(i=2;i<=m;i++)
	{
		while( fix && s[fix+1]!=s[i] ) fix=next[fix];
		if( s[fix+1]==s[i] ) ++fix;
		next[i]=fix;
	}
	for(i=0;i<m;i++)
		for(j='0';j<='9';j++)
		{
			fix=i;
			while( fix && s[fix+1]!=j ) fix=next[fix];
			if( j==s[fix+1] ) b[i][fix+1]++;
			else b[i][0]++;
		}
}
void Quick_Power(int x)
{
	while(x)
	{
		if(x&1)a*=b;
		b*=b;
		x>>=1;
	}
}
int main()
{
	int i;
	cin>>n>>m>>p;
	scanf("%s",s+1);
	KMP();
	for(i=0;i<m;i++)
		a[i][i]=1;
	Quick_Power(n);
	for(i=0;i<m;i++)
		ans+=a[0][i],ans%=p;
	cout<<ans<<endl;
}


版权声明:本文博客原创文章,博客,未经同意,不得转载。





本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4679508.html,如需转载请自行联系原作者


相关文章
|
25天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
1月前
|
机器学习/深度学习 算法 搜索推荐
django调用矩阵分解推荐算法模型做推荐系统
django调用矩阵分解推荐算法模型做推荐系统
27 4
|
1月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
101 0
|
1月前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
19 0
|
1月前
|
算法
KMP算法
KMP算法
30 0
|
3月前
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
4月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
119 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
3月前
|
算法
KMP算法
KMP算法
27 0
|
4月前
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用