Tag Archives: KMP

[KMP+数位DP+矩阵快速幂]BZOJ1009GT考试

Cptraser/ 十月 29, 2018/ 2018.10/ 0 comments

[HNOI2008]GT考试 神奇的KMP矩乘,从普及组A到提高组… 题面传送门 我们表示长串匹配到,短串匹配到的吉利的方案数。 设表示失配的方案数。 考虑转移: ,表示失配后短串匹配到哪个位置。 ?好像我们会!!! 可以先构造,原式写为: 可以看成矩乘:     然后上快速幂。

Read More

NOIP赛前整理~KMP

Cptraser/ 十月 24, 2018/ 2018.10/ 0 comments

KMP~从入门到放弃 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个nex

Read More