KMP算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了KMP算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1916字,纯文字阅读大概需要3分钟。
内容图文
![KMP算法](/upload/InfoBanner/zyjiaocheng/639/d661051cb0c2420e961fc820e67dcb6d.jpg)
#include<stdio.h> #include<stdlib.h> #include<string.h> //复杂版 void prefix_table(char pattern[],int prefix[],int n){ prefix[0] = 0; int len = 0; int i = 1; while (i < n){ if (pattern[i] == pattern[len]){ len++; prefix[i] = len; i++; } else{ if (len > 0){ len = prefix[len - 1]; } else{ prefix[i] = len; i++; } } } } int move_prefix_table(int prefix[],int n){ int i; for(i=n-1;i>0;i--){ prefix[i] = prefix[i-1]; } prefix[0] = -1; } void kmp_search(char text[],char pattern[]){ int n = strlen(pattern); int m = strlen(text); int *prefix = (int*)malloc(sizeof(int)*n); prefix_table(pattern,prefix,n); move_prefix_table(prefix,n); // text[i] , len(text) = m // pattern[j], len(pattern) = n int i = 0; int j = 0; while (i < m){ if (j == n - 1 &&text[i] == pattern[j]){ printf("Found patern at %d\n", i - j ); j = prefix[j]; for (int x=0;x<n;x++){ printf("%c",pattern[x]); } } if (text[i] == pattern[j]){ i++; j++; } else{ j = prefix[j]; if (j == -1){ i++; j++; } } } } int main(){ char pattern[] = "ABABCABAA"; char text[] = "ABABABCABAABABABAB"; kmp_search(text,pattern); /* int prefix[9]; int n = 9; prefix_table(pattern,prefix,n); move_prefix_table(prefix,n); int i; for (i = 0;i < n;i++){ printf("%d\n",prefix[i]); } */ return 0; }
1 #include<stdio.h> 2 #include<string.h> 3 #define maxn (int)1e5+8 4 char pattern[maxn]= {0},text[maxn]= {0}; 5 int next[maxn]= {0}; 6 void Next(char *s,int *fail) { 7 fail[0]=-1,fail[1]=0; 8 int len=strlen(s); 9 for(int i=1,j=0;i<len;) { 10 if(j==-1||s[i]==s[j])fail[++i]=++j; 11 else j=fail[j]; 12 } 13 } 14 int KmpSearch(char* s, char* p) { 15 int i = 0,j = 0,sLen = strlen(s),pLen = strlen(p); 16 while (i < sLen && j < pLen) { 17 if (j == -1 || s[i] == p[j]) 18 i++,j++; 19 else j = next[j]; 20 } 21 return j == pLen?i - j:-1; 22 } 23 int main() { 24 scanf("%s%s",pattern,text); 25 Next(pattern,next); 26 printf("%d\n",KmpSearch(text,pattern)); 27 }
内容总结
以上是互联网集市为您收集整理的KMP算法全部内容,希望文章能够帮你解决KMP算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。