欢迎来到入门教程网!

C语言

当前位置:主页 > 软件编程 > C语言 >

KMP 算法实例详解

来源:本站原创|时间:2020-01-10|栏目:C语言|点击:

KMP 算法实例详解

KMP算法,是由Knuth,Morris,Pratt共同提出的模式匹配算法,其对于任何模式和目标序列,都可以在线性时间内完成匹配查找,而不会发生退化,是一个非常优秀的模式匹配算法。

分析:KMP模板题、KMP的关键是求出next的值、先预处理出next的值、然后一遍扫过、复杂度O(m+n)

实例代码:

#include<stdio.h> 
#include<string.h> 
#define N 1000005 
int s[N]; 
int p[N]; 
int next[N]; 
int m,n; 
void getnext(){ 
 int j=0,k=-1; 
 next[0]=-1; 
 while(j<m){ 
  if(k==-1||p[j]==p[k]){ 
   j++; 
   k++; 
   next[j]=k; 
  } 
  else 
   k=next[k]; 
 } 
} 
int kmp(){ 
 int i=0,j=0; 
 getnext(); 
 while(i<n){ 
  if(j==-1||s[i]==p[j]){ 
   i++; 
   j++; 
  } 
  else 
   j=next[j]; 
  if(j==m) 
   return i; 
 } 
 return -1; 
} 
int main(){ 
 int t; 
 scanf("%d",&t); 
 while(t--){ 
  scanf("%d%d",&n,&m); 
  for(int i=0;i<n;i++) 
   scanf("%d",&s[i]); 
  for(int i=0;i<m;i++) 
   scanf("%d",&p[i]); 
  if(kmp()==-1) 
   printf("-1\n"); 
  else 
   printf("%d\n",kmp()-m+1); 
 } 
 return 0; 
} 

以上就是KMP 算法的实例详解本站关于数据结构和算法的文章还有很多,希望大家搜索查阅,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

上一篇:浅谈C++ Socket编程

栏    目:C语言

下一篇:C语言实现2048游戏

本文标题:KMP 算法实例详解

本文地址:https://www.xiuzhanwang.com/a1/Cyuyan/1313.html

网页制作CMS教程网络编程软件编程脚本语言数据库服务器

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:835971066 | 邮箱:835971066#qq.com(#换成@)

Copyright © 2002-2020 脚本教程网 版权所有