Category Archives: KMP

CodeForces 526D Om Nom and Necklace (KMP)

给出一个字符串计算他的每个前缀是否能够变成ABAB….A的形式,A出现k+1次,B出现k次. 对于 …

LightOJ 1334 Genes in DNA (KMP)

给出两个串A和B,问B的任意两个前后缀组合(有(n-1) * (n-1)种可能)的串在A中出现次数的总和. 可 …

HDU 4763 Theme Section (KMP,网上的算法都是垃圾!)

给出一个字符串,找出最大的一个子串满足即能和前缀匹配也能和反向的前缀匹配,但是不能重叠! 开始想到的算法就是枚 …

POJ 3167 Cow Patterns (kmp,好题)

B串去匹配A串,如果匹配成功的规则是串中每个对应的数字的RANK大小要一样。 根据kmp的匹配,我们只要维护一 …

HUST 1010 The Minimum Length (最小重叠子串,kmp)

原串重复很多次,然后从中间任选一段假设是B,现在给出B,求最小的原串长度。 分析不难发现其实就是求最小重叠子串 …

POJ 2185 Milking Grid (最小覆盖矩阵,kmp)

一个字符矩阵求最小覆盖矩阵,最小覆盖矩阵即最小覆盖子串的扩展,最小覆盖子串长度 = len – n …

hdu 4333 Revolving Digits (扩展KMP)

题意:一个串可以将一些后缀放到串前面构成新串,求所有的新串中大于原串等于原串小于原串的个数。 题解:直接扩展k …

CSU 1581 Clock Pictures (KMP)

题意:一种钟有n个指针,现在给出两个这样钟的指针角度,然后判断两个钟是是否可以通过旋转得到匹配。 题解:排序后 …

Codeforces 535D Tavas and Malekas (KMP)

题意:一个长度为n的原串s,有m个位置被另外一个串t匹配,然后给出字符串t以及m个匹配开始位置,求s串可能有多 …