首页 > 代码库 > 串-KMP模式匹配算法(nextval数组)
串-KMP模式匹配算法(nextval数组)
#include <stdio.h> #include <stdlib.h> #include <string.h> void get_next(char T[100],int *next); int Index_KMP(char S[100],char T[100],int pos); int main() { int n; char S[100],T[100]; gets(S); gets(T); n=Index_KMP(S,T,2); printf("%d",n); return 0; } void get_nextval(char T[100],int *nextval) { int j,i; int t; nextval[0]=-1; j=-1; i=0; t=strlen(T); while(i<t) { if(j==-1||T[j]==T[i]) { i++; j++; if(T[i]!=T[j]) nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } } int Index_KMP(char S[100],char T[100],int pos) { int i,j; int s,t; i=pos; j=0; int nextval[100]; get_nextval(T,nextval); s=strlen(S); t=strlen(T); while(i<s&&j<t) { if(j==-1||S[i]==T[j]) { j++; i++; } else j=nextval[j]; } if(j>=t) { return (i-t+1); } else return 0; }
实战总结:因为是朴素模式匹配算法的改进所以只由先理解了next函数的定义,才能容易理解nextval函数。
串-KMP模式匹配算法(nextval数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。