`

KMP算法详解及各种应用

阅读更多

KMP算法详解:
KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。
在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。
对于next[]数组的定义如下:
1) next[j]=-1 j=0
2) next[j]=max k:0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j]=0 其他
如:
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0时,表示P[0...k-1]=P[j-k,j-1]
因此KMP算法的思想就是:在匹配过程称,若发生不匹配的情况,如果next[j]>=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next[j]=-1,则将i右移1位,并将j置0,继续进行比较。
代码实现如下:

[cpp]view plaincopy
 
  1. intKMPMatch(char*s,char*p)
  2. {
  3. intnext[100];
  4. inti,j;
  5. i=0;
  6. j=0;
  7. getNext(p,next);
  8. while(i<strlen(s))
  9. {
  10. if(j==-1||s[i]==p[j])
  11. {
  12. i++;
  13. j++;
  14. }
  15. else
  16. {
  17. j=next[j];//消除了指针i的回溯
  18. }
  19. if(j==strlen(p))
  20. returni-strlen(p);
  21. }
  22. return-1;
  23. }

因此KMP算法的关键在于求算next[]数组的值,即求算模式串每个位置处的最长后缀与前缀相同的长度, 而求算next[]数组的值有两种思路,第一种思路是用递推的思想去求算,还有一种就是直接去求解。
1、按照递推的思想:
根据定义next[0]=-1,假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]
1)若P[j]==P[k],则有P[0..k]==P[j-k,j],很显然,next[j+1]=next[j]+1=k+1;
2)若P[j]!=P[k],则可以把其看做模式匹配的问题,即匹配失败的时候,k值如何移动,显然k=next[k]。
因此可以这样去实现:

[cpp]view plaincopy
 
  1. voidgetNext(char*p,int*next)
  2. {
  3. intj,k;
  4. next[0]=-1;
  5. j=0;
  6. k=-1;
  7. while(j<strlen(p)-1)
  8. {
  9. if(k==-1||p[j]==p[k])//匹配的情况下,p[j]==p[k]
  10. {
  11. j++;
  12. k++;
  13. next[j]=k;
  14. }
  15. else//p[j]!=p[k]
  16. k=next[k];
  17. }
  18. }

2、直接求解方法

[cpp]view plaincopy
 
  1. voidgetNext(char*p,int*next)
  2. {
  3. inti,j,temp;
  4. for(i=0;i<strlen(p);++i)
  5. {
  6. if(i==0)
  7. {
  8. next[i]=-1;//next[0]=-1
  9. }
  10. elseif(i==1)
  11. {
  12. next[i]=0;//next[1]=0
  13. }
  14. else
  15. {
  16. temp=i-1;
  17. for(j=temp;j>0;--j)
  18. {
  19. if(equals(p,i,j))
  20. {
  21. next[i]=j;//找到最大的k值
  22. break;
  23. }
  24. }
  25. if(j==0)
  26. next[i]=0;
  27. }
  28. }
  29. }
  30. boolequals(char*p,inti,intj)//判断p[0...j-1]与p[i-j...i-1]是否相等
  31. {
  32. intk=0;
  33. ints=i-j;
  34. for(;k<=j-1&&s<=i-1;k++,s++)
  35. {
  36. if(p[k]!=p[s])
  37. returnfalse;
  38. }
  39. returntrue;
  40. }

http://poj.org/problem?id=2406

 

给定一个字符串,问最多是多少个相同子串不重叠连接构成。

KMP的next数组应用。这里主要是如何判断是否有这样的子串,和子串的个数。

若为abababa,显然除其本身外,没有子串满足条件。而分析其next数组,next[7] = 5,next[5] = 3,next[3] = 1,即str[2..7]可由ba子串连接构成,那怎么否定这样的情况呢?很简单,若该子串满足条件,则len%sublen必为0。sunlen可由上面的分析得到为len-next[len]。

因为子串是首尾相接,len/sublen即为substr的个数。

若L%(L-next[L])==0,n = L/(L-next[L]),else n = 1

[cpp]view plaincopy
 
  1. #include<iostream>
  2. #include<cstdio>
  3. usingnamespacestd;
  4. charpattern[1000002];
  5. intnext[1000002];
  6. /*
  7. kmp算法,需要首先求出模式串的next函数值
  8. next[j]=k,说明p0pk-1==pj-kpj-1,也就是说k为其前面相等串的长度
  9. */
  10. voidget_nextval(constchar*pattern)
  11. {
  12. inti=0,j=-1;
  13. next[0]=-1;
  14. while(pattern[i]!='\0')
  15. {
  16. if(j==-1||pattern[i]==pattern[j])//pattern[i]表示后缀的单个字符,pattern[j]表示前缀的单个字符
  17. {
  18. ++i;
  19. ++j;
  20. if(pattern[i]!=pattern[j])
  21. next[i]=j;
  22. else
  23. next[i]=next[j];
  24. }
  25. else
  26. j=next[j];//若j值不相同,则j值回溯
  27. }
  28. }//get_nextval
  29. intmain(void)
  30. {
  31. intlen;
  32. while(scanf("%s",pattern)!=EOF)
  33. {
  34. if(pattern[0]=='.')
  35. break;
  36. len=strlen(pattern);
  37. get_nextval(pattern);
  38. if(len%(len-next[len])==0)
  39. printf("%d\n",len/(len-next[len]));
  40. else
  41. printf("1\n");
  42. }
  43. return0;
  44. }

http://poj.org/problem?id=1961

大意:
定义字符串A,若A最多由n个相同字串s连接而成,则A=s^n,如"aaa" = "a"^3,"abab" = "ab"^2
"ababa" = "ababa"^1

给出一个字符串A,求该字符串的所有前缀中有多少个前缀SA= s^n(n>1)
输出符合条件的前缀长度及其对应的n

如aaa
前缀aa的长度为2,由2个'a'组成
前缀aaa的长度为3,由3个"a"组成

分析:KMP
若某一长度L的前缀符合上诉条件,则
1.next[L]!=0(next[L]=0时字串为原串,不符合条件)
2.L%(L-next[L])==0(此时字串的长度为L/next[L])

对于2:有str[0]....str[next[L]-1]=str[L-next[L]-1]...str[L-1]
=》str[L-next[L]-1] = str[L-next[L]-1+L-next[L]-1] = str[2*(L-next[L]-1)];
假设S = L-next[L]-1;则有str[0]=str[s]=str[2*s]=str[3*s]...str[k*s],对于所有i%s==0,均有s[i]=s[0]
同理,str[1]=str[s+1]=str[2*s+1]....
str[j]=str[s+j]=str[2*s+j]....
综上,若L%S==0,则可得L为str[0]...str[s-1]的相同字串组成,
总长度为L,其中字串长度SL = s-0+1=L-next[L],循环次数为L/SL
故对于所有大于1的前缀,只要其符合上述条件,即为答案之一

[cpp]view plaincopy
 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. usingnamespacestd;
  5. charpattern[1000002];
  6. intnext[1000002];
  7. /*
  8. kmp算法,需要首先求出模式串的next函数值
  9. next[j]=k,说明p0pk-1==pj-kpj-1,也就是说k为其前面相等串的长度
  10. */
  11. voidget_nextval(constchar*pattern)
  12. {
  13. inti=0,j=-1;
  14. next[0]=-1;
  15. while(pattern[i]!='\0')
  16. {
  17. if(j==-1||pattern[i]==pattern[j])
  18. {
  19. ++i;
  20. ++j;
  21. next[i]=j;
  22. }
  23. else
  24. j=next[j];
  25. }
  26. }//get_nextval
  27. intmain(void)
  28. {
  29. inti,len,n,j=1;
  30. while(scanf("%d",&n)!=EOF)
  31. {
  32. if(!n)
  33. break;
  34. scanf("%s",pattern);
  35. len=strlen(pattern);
  36. get_nextval(pattern);
  37. printf("Testcase#%d\n",j++);
  38. for(i=2;i<=len;i++)
  39. {
  40. if(i%(i-next[i])==0&&i/(i-next[i])>1)
  41. printf("%d%d\n",i,i/(i-next[i]));
  42. }
  43. printf("\n");
  44. }
  45. return0;
  46. }

http://poj.org/problem?id=2752
大意:
给出一个字符串A,求A有多少个前缀同时也是后缀,从小到大输出这些前缀的长度。

分析:KMP
对于长度为len的字符串,由next的定义知:
A[0]A[1]...A[next[len]-1]=A[len-next[len]]...A[len-1]此时A[0]A[1]...A[next[len]-1]为一个符合条件的前缀
有A[0]A[1]....A[next[next[len]]-1] = A[len-next[next[len] - next[next[len]]]...A[next[len]-1],故A[0]A[1]....A[next[next[len]]-1]也是一个符合条件的前缀
故从len=>next[len]=>next[next[len]] ....=>直到某个next[]为0均为合法答案,注意当首位单词相同时,也为答案。

[cpp]view plaincopy
 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<vector>
  5. usingnamespacestd;
  6. charpattern[400002];
  7. intnext[400002];
  8. /*
  9. kmp算法,需要首先求出模式串的next函数值
  10. next[j]=k,说明p0pk-1==pj-kpj-1,也就是说k为其前面相等串的长度
  11. */
  12. voidget_nextval(constchar*pattern)
  13. {
  14. inti=0,j=-1;
  15. next[0]=-1;
  16. while(pattern[i]!='\0')
  17. {
  18. if(j==-1||pattern[i]==pattern[j])
  19. {
  20. ++i;
  21. ++j;
  22. next[i]=j;
  23. }
  24. else
  25. j=next[j];
  26. }
  27. }//get_nextval
  28. intmain(void)
  29. {
  30. inti,len,n;
  31. vector<int>ans;
  32. while(scanf("%s",pattern)!=EOF)
  33. {
  34. ans.clear();
  35. len=strlen(pattern);
  36. get_nextval(pattern);
  37. n=len;
  38. while(n)
  39. {
  40. ans.push_back(n);
  41. n=next[n];
  42. }
  43. if(pattern[0]==pattern[n-1])//首部、尾部字符相同
  44. ans.push_back(1);
  45. i=ans.size()-1;
  46. for(;i>0;i--)
  47. printf("%d",ans[i]);
  48. printf("%d\n",ans[0]);
  49. }
  50. return0;
  51. }
分享到:
评论

相关推荐

    asp代码ASP家教信息管理系统(源代码+论文)

    asp代码ASP家教信息管理系统(源代码+论文)本资源系百度网盘分享地址

    基于ssm高校毕业选题管理系统.zip

    基于ssm高校毕业选题管理系统.zip

    基于旷视研究院领先的深度学习算法,提供满足多业务场景的预训练模型.zip

    人工智能毕业设计&课程设计

    tensorflow_model_optimization-0.1.3.dev0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_model_analysis-0.15.0-py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    粒子群算法.docx 粒子群算法(Particle Swarm Optimization,PSO)是一种优化算法,受到鸟群或鱼

    粒子群算法 粒子群算法(Particle Swarm Optimization,PSO)是一种优化算法,受到鸟群或鱼群等群体行为的启发。该算法通过模拟群体中个体之间的合作和竞争来搜索最优解。粒子群算法通常用于解决连续优化问题。 ### 工作原理: 1. **初始化**:随机生成一群粒子(也称为个体),每个粒子代表搜索空间中的一个解,并随机初始化其位置和速度。 2. **评估**:根据每个粒子的位置,计算其对应的适应度值(目标函数值)。 3. **更新**:根据个体最优和全局最优的情况,更新每个粒子的速度和位置。粒子会根据自己历史最好的位置以及整个群体历史最好的位置进行调整,以期望更好的搜索方向。 4. **迭代**:重复评估和更新步骤,直到满足停止条件(如达到最大迭代次数、目标函数值足够接近最优解等)。 ### 主要参数: - 粒子数量(Population Size):群体中粒子的数量,通常越大越容易找到全局最优解,但计算成本也会增加。 - 惯性权重(Inertia Weight):控制粒子运动的惯性,平衡局部搜索和全局搜索能力。通常随着迭代次数增加而逐渐减小。

    20210327 AI-for-Drug-Discovery-2020.pdf

    20210327 AI-for-Drug-Discovery-2020

    tensorflow_model_optimization-0.1.2-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    Linux创建虚拟机的步骤

    Linux创建虚拟机的步骤

    基于SpringBoot的校园二手书交易管理系统设计源码

    这是一个基于SpringBoot开发的校园二手书交易管理系统,使用Java语言,包含102个文件。主要文件类型包括39个Java源文件、23个HTML文件、10个PNG图片文件、9个XML文件、9个JavaScript文件、4个CSS文件、2个Markdown文档、2个JPG图片文件、1个gitignore文件和1个SVG文件。该项目简洁易用,采用的技术经典,非常适合Java项目入门学习和企业级Java开发熟悉,提供了二手书交易管理、用户认证、数据统计等功能,旨在为校园内的二手书交易提供一个便捷、安全的平台。

    基于SSM的旅游管理系统.zip

    基于SSM的旅游管理系统.zip

    基于ssm框架网络财务设计与实现.zip

    基于ssm框架网络财务设计与实现.zip

    三菱PLC例程源码PLC同变频器通讯程序3

    三菱PLC例程源码PLC同变频器通讯程序3本资源系百度网盘分享地址

    基于ssm+jsp网上茶叶销售平台.zip

    基于ssm+jsp网上茶叶销售平台.zip

    通信专业毕业设计(论文)-企业网通信方案设计

    随着网络和科学技术的飞速发展,网络建设作为信息化建设的基础,也越来越受到企业的重视,网络结构和网络信息安全都是企业信息化建设中需要解决的重要问题。 本设计出于对众宇通讯公司长期稳定发展的考虑,针对公司的现状和发展需求,为公司设计了一个稳定的、相对安全的、可扩展并且可以支撑必要的网络应用的网络结构。在此次设计中,主要的运用到的技术与实现功能有:(1)汇聚交换机上使用DHCP技术,使各个接入层设备可自动获取相应的IP地址,也避免了IP地址的冲突;(2)运用VRRP技术,增强网络的连续性和稳定性,实现多链路备份冗余和网关备份冗余;(3)运用MSTP技术,将不同的VLAN与相应实例捆绑,避免了网络环路和广播风暴的产生;(4)通过防火墙技术,实现了企业内部与外部网络之间的信息交互安全。除此之外,还进行了VLAN的划分,端口安全设置,ACL访问限制,NAT地址转换,使用OSPF协议、静态路由等网络配置。 本论文基于华为ENSP仿真模拟软件,充分考虑到了整个公司网络今后的实用性、安全性以及可扩展性。利用所学的相关知识和网络技术,对众宇通讯公司的网络进行模拟设计。此设计根据三层网络结构来搭建网络拓扑,

    Gromacs中文手册5.0.2.pdf

    Gromacs中文手册5.0.2

    三菱PLC例程源码八层以下货梯通用程序(奥菱达)

    三菱PLC例程源码八层以下货梯通用程序(奥菱达)本资源系百度网盘分享地址

    seg.v

    seg.v

    ftqqzx.zip

    ftqqzx.zip

    基于tensorflow深度学习的中文机器阅读理解-完形填空.zip

    人工智能毕业设计&课程设计

Global site tag (gtag.js) - Google Analytics