1. 1、本文档共102页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
ACM模板-

字符串处理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]-

文档评论(0)

haihang2017 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档