青竹qingzhu

KMP

AC自动机(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

全部文章 / KMP （共3篇）

2020牛客暑期多校训练营（第二场）A kmp+hash

题意对于字符串s,t,定义f(s,t)为s的前缀和t的后缀的最长匹配长度。给n个字符串,求题解预处理出n个字符串所有后缀的hash值，并记录个数。枚举每一个字符串的所有前缀，求出前缀的hash值，答案加上与前缀相同hash值的后缀个数就行，但是因为要求的是si和sj的最长前后缀长度，例如si...

2020-07-22

0 510

LightOJ - 1334 Genes in DNA KMP 求贡献思想

Genes in DNA 题意给一个文本串和一个模式串，求模式串的所有前缀与后缀的组合在文本串里出现次数和。当我觉得我懂KMP的时候，KMP给了我一巴掌：不，你不懂！思路这题朴素的算法就是把模式串的前缀和后缀组合列出来，跑KMP求出现次数和。显然数据范围不允许，那考虑求贡献的方法，对于文本...

2020-07-13

0 403

栗酱的数列连续子序列和相等——kmp

传送门题意栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A’，满足(a’1+b1)%k = (a’2+b2)%k = …… = (a’m + bm)%k。思路按照题目给的条件式只能暴力做，暴力做又超时。那么对满足式进行修改，(a[i]+b[i])...

2020-07-13

0 442