ACM模板-.docx

字符串处理31、kmp算法32、扩展kmp43、字符串最小表示法64、Manacher75、字典树96、最小包含子串117、Aho-Corasick automaton148、字符串Hash189、Suffix Array20杂项22数据结构221、并查集222、线段树263、树状数组274、RMQ305、单调队列 单调栈306、分块31杂项32动态规划321、整数划分322、区间DP333、数位DP354、状压DP37杂项37图论391、最短路径402、最小生成树（MST）433、LCA、树的重心、树的直径444、图的割点、割边、点双、边双485、有向图的强连通分量526、二分图匹配537、欧拉回路、哈密顿回路、拓扑排序578、网络流58杂项60计算几何611、基本公式612、正N边形公式643、平面最近对654、欧拉公式，分割平面67数学681、组合数Cnm 防溢出公式682、各种素数筛法723、快速幂、矩阵734、数字特征、约数个数765、扩展欧几里德算法和求逆元776、各种数列817、米勒测试和大数分解828、欧拉函数eular 、Mobius反演849、AntiPrime8610、万能积分公式---simpson8811、高斯消元89杂项90其他941、STL942、常量定义 手动开栈 C++取消同步 int范围963、三分答案974、高精度、输入挂、java大数985、基本思考方式101杂项102字符串处理1、kmp算法主串：匹配串。子串：模式串。子串先自己匹配，得到next[]，然后再和主串进行匹配，匹配时主串的i值不回溯，所以使得整个算法的复杂度压缩为O(lenstr+lensub),关于next[]数组的意义:next[i]的意思是，匹配到当前第i个字符，如果那个字符和主串当前的匹配字符不搭配，那么就跳转到sub[]中的第next[i]个字符匹配。为什么能这样做呢？那是因为子串中，前缀(1--next[i]-1)和后缀(begin--i-1)是完全相等的，begin的值各不相同，例如abcabc中，next[len]=3(不包括最后那个c的)，那么就是[1--2]和[4,5]是完全相等的，next[len+1]=4,也就是[1--3]和[3--6]是完全相等的。那么这样的话，next[i]的意思就是在长度为i-1中的子串中，最长的前缀-后缀的长度为next[i]-1。因为next[i]是告诉我们应该跳去哪里匹配，是越界的。void get_next(char sub[], inttonext[], int lensub) {int i =1, j =0;tonext[1] =0; //记得初始值不能忘记//tonext[lensub +1]这个也有值了后面的++i和++j先加后赋值while (i = lensub) { //sub[i]的含义，后缀的单个字符//sub[j]的含义，前缀的单个字符if (j ==0|| sub[i] == sub[j]) { //考虑的是上一个的tonext[++i] =++j; //用是上一个的比较，值的当前的值 } else j =tonext[j]; }}返回主串str[]中子串sub[]的出现次数，(允许重叠的部分),这里的重叠部分就是说：例如aaa,则aa出现的次数为2次。 pos为在主串的第pos个位置开始匹配，默认为1int kmp(char str[], char sub[], int pos) {int lenstr= strlen(str +1);int lensub= strlen(sub +1);inttonext[maxn] = {0}; //maxn为最大长度 get_next(sub, tonext, lensub); //得到next[]数组int i = pos; //从哪里出发，i变量是主串的。int j =1; // j变量是子串的。int ans =0;while (i = lenstr) {if (j ==0|| str[i] == sub[j]) { i++; j++; } else j =tonext[j];if (j == lensub+1) { //有一个了 ans++; j =tonext[j]; //回溯匹配 //i值不用回溯的 } }return ans;}KMP求循环节：1=cirlenstr当next[lenstr+1]=1时，求出来的并不是循环节！此时cir=lenstrcir=lenstr-(next[lenstr+1]-