KMP补题

作者: 99hgz 分类: kmp 发布时间: 2099-12-31 15:49

划水现场

以下全是口胡,不保证正确性

Codeforces 432D  求出fail数组,第一个答案就是从st[n]开始跳fail指针所到的位置,第二问可以维护一个s数组,s[i]表示st[1..i]出现了几次。首先s[i]的初值为1,当出现一个j==next[i]时,说明st[1..j]在所有等于st[1..i]的串中,那个倒序更新这个数组s[next[i]]+=s[i]即可(当然用sam水一发就好了)

Codeforces 126B 求出fail数组,然后同上(用sam水一发)

Codeforces 631D 把相邻的相同字符拼接起来,对于匹配串只有一位的情况,线扫统计,剩下的将匹配串的前缀后缀等一个字母特判,中间的部分用hash进行判断。

「NOI2014」动物园 先考虑暴力求解答案的过程,记忆化一下就好了

[Lydsy1708月赛]字符串大师 将最短循环节长度转化为next数组,即next[i]=i-xunhuan[i]。从前到后贪心选取,当next[i]!=0时,这位必须要填st[i-next[i]],否则这位不能填i-1及它的所有fail指针的

Poj 3461 同126B

Cogs 2510 思博题

51nod 1129 同上面的方法dp求一个s数组

Codeforces 346B Dp一下,f[i][j][k]表示s1[i]匹配上s2[j]且匹配到virus[k]时得到的最长公共子序列长度,不匹配时往fail跳。

Codeforces 625B 贪心,一个子串把#放在最后一定是最优的,然后继续匹配即可

Codechef PATTMATC 把匹配串按照*号分割,分别建kmp。在主串上枚举起点,依次到kmp上匹配,要使得匹配位置不重叠且递增,这个位置应该是对应递增的,所以可以从上次的答案出开始继续匹配 ,好像有点细节问题。

Codechef TASHIFT exkmp裸题,将原串复制两遍即可

Codeforces 808G 26*s*t Dp一下

Codeforces 825F dp[i]表示表达前缀i需要的长度,枚举j转移一下,可以hash或kmp判断循环节长度

[POI2006]OKR i-fail[i]获得最短循环节长度,往fail处跳来得到最长循环节长度

感觉快收集完市面上的题了…其实很多还是比较水的

Codeforces 30E 考虑枚举前缀或中间的回文串,枚举前缀应该需要预处理中间的O(n)个回文串,还得用个数据结构=维护,感觉已经带了两个lg,不好。考虑枚举middle,因为suffix是原串的后缀,可以二分一个长度len,考虑所有≤len的后缀的反串的第一次出现位置是否与middle重叠。则要预处理q[i]表示S[i..n]这个后缀的反串的第一次出现位置。好像可以把后缀放到sam上匹配一波带走,也可以用个kmp,因为后缀的反串相当于是在前一个串后面加了一个字母,那么我们只要先找到匹配上长度为1的位置,再保留kmp的状态,继续匹配长度为2的串,这样显然是对的。

SRM 557 D2-1000 需要转化的dp,类似GT考试,但直接转移即可

SPOJ PRETILE =POI2006 OKR

SPOJ ARDA1 二维kmp,hash即可

UVA 11475

发表评论

电子邮件地址不会被公开。 必填项已用*标注