本文内容框架：§1Boyer-Moore算法§2Horspool算法§3Sunday算法§4KMP算算法§5KR算法§6AC自动机§7小结  §1Boyer-Moore（BM）算法 Boyer-Moore算法原...

sub[]代表子串，str[]代表原串，next[]代表当sub[i]!=str[j]时，子串需要跳到的地方，实现代码如下：获取next数组的代码：1voidGetNext()//求子串中的相同的真前缀和真后缀2{3memset(next,0,sizeof(next));4next[0]=-1;5inti=0,j=-1...

UVALive3026   KMP中next[]数组的应用；题意：给出一个字符串，问该字符串每个前缀首字母的位置和该前缀的周期。思路：裸KMP直接上就是了；设该字符串为str，str字符串的长度为len，next[]的有关前缀的周期的性质：如果len%（len-next[len]）=&nb...

　　一个串T是S的循环节，当且仅当存在正整数k，使得S是T^k(即T重复k次)的前缀，比如abcd是abcdabcdab的循环节。给定一个长度为n的仅由小写字符构成的字符串S，请对于每个k(1<=k<=n)，求出S长度为k的前缀的最短循环节的长度per_i。字符串大师小Q觉得这个问题过于简单，于是花了一分钟...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ172.html首先，这个问题显然是个背包问题。然后，可以证明：一个字符串的border长度可以划分成$O(log|S|)$个等差数列。(以下图片摘自 金策-《字符串算法选讲》)由于长度n可以随便取，所以我们可以在对n...

原文链接https://www.cnblogs.com/zhouzhendong/p/CF109D.html　　给定两个字符串$a,b$，求一组$i,j$使得$f(a,i,j)=b$。如果无解输出"-1-1"，如果多组解，输出i尽量大的；如果i相同，输出j尽量小的。　　其中$f(s,i,j)=s[i+1cdotsj-1...

原文链接https://www.cnblogs.com/zhouzhendong/p/CF1017E.html　　给定两个点集，并构成两个凸包。　　问这两个凸包是否可以通过旋转和平移重合。　　每一个凸包的点数$leq10^5$。　　建两个凸包，注意一下，建出来的凸包要避免凸包外围连续三点共线。　　然后把每一个凸包的边长...

原文链接https://www.cnblogs.com/zhouzhendong/p/CF235C.html　　给定一个字符串$s$，多组询问，每组询问的形式为一个字符串$T$，问$S$有多少个子串与$T$循环同构。（如果$S$有多个相同子串都同构，则算多次）　　$|S|leq10^6,sum|T|leq10^6$　　...

原文链接https://www.cnblogs.com/zhouzhendong/p/CF117G2.html　　定义斐波那契字符串如下：　　$s_1="a"$　　$s_2="b"$　　$s_i=s_{i-1}+s_{i-2}(igeq3)$　　给定$k,m$，以及对应的$m$组询问。　　每组询问一个字符串$x$，问$...

原文链接https://www.cnblogs.com/zhouzhendong/p/9253173.html　　找一个串$w$满足：　　1、$w$是$s_1$的子串　　2、$w$是$s_2$的子串　　3、$s_3$不是$w$的子串　　4、$w$的长度应尽可能大　　输出$w$的长度。　　$|s_1|,|s_2|leq5...

　　给T组数据，每组数据给一个长度为n的字符串s。求字符串每个前缀出现的次数和，结果mod10007。　　首先闭着眼睛KMP跑一跑。　　然后我们来dp。　　dp[i]表示以第i位结尾的前缀个数。　　那么，根据Next的含义，不难写出dp[i]=dp[Next[i]]+1的转移方程式。　　然后就OK了。#include&...

　　给T组数据，每组有长度为n和m的母串和模式串。判断模式串是否是母串的子串，如果是输出最先匹配完成的位置，否则输出-1.　　KMP裸题。#include<cstring>#include<algorithm>#include<cstdio>#include<cstdlib&g...

TimeLimit:10000/5000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):27028    AcceptedSubmissi...

1intkmpnext[N];2chars[N],t[N];///s为主串，t为模式串3intslen,tlen;///slen为主串的长度，tlen为模式串的长度4inlinevoidgetnext()5{6inti,j;7j=kmpnext[0]=-1;8i=0;9while(i<tlen)10{11if(j...

1277字符串中的最大值题目来源：Codility基准时间限制：1秒空间限制：131072KB分值:80难度：5级算法题一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：abcd的所有前缀为a,ab,abc,abcd。给出一个字符串S，求其所有前缀中，字符长度与出现次数的乘积的最大值。例如：S="abababa...