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...

1.SetSet是一个集合，里面的值都是唯一的，没有重复的。Set中可以是任何数据类型，并且添加数据时会进行严格比较，重复数据无法加入。2.WeakSet弱引用Set。只能存储对象，不能存储其他类型。且只保持对其中对象的弱引用，若外部无对此对象的引用，或者对象被删除，则WeakSet中将不再有此对象。因为成员都是弱引用...

原文链接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...

原文链接http://www.cnblogs.com/zhouzhendong/p/8284763.html　　直接描述输入吧　　首先一个T(T<15)，表示数据组数。　　每组数据，首先三个数：len,k,m，分别表示接下来要读入的字符串的长度、每一个字符串中出现的不同字母个种类数、询问的字符串数。(len<...

原文链接http://www.cnblogs.com/zhouzhendong/p/8284304.html　　给一个n的点m条边的有向图。　　然后让你把这个图分成许多环，问环中边权和最小为多少。　　题目保证一定存在合法的方案。　　我们把每一个点扯成两个点。　　一个专门接受入度，一个专门接受出度，然后就是KM裸题了。　...

原文链接http://www.cnblogs.com/zhouzhendong/p/8284105.html（来自谷歌翻译）　　这是一道好题。　　我们首先把所有边权都乘上(n+1)。　　然后对于原来就有的边，我们再+1.　　然后跑一跑KM，利用的原边数就是ans%(n+1)，最终方案的效果就是ans/(n+1)　　为什...

　　给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...

说明：配置好网桥之后一定要重启，不然不生效。这个是Desktop版GUI设置的问题。Server版不会。配置： 参考：http://www.jb51.net/LINUXjishu/333778.html（以上图片转自此篇文章）...