这个KMP算法效率有点问题。有个地方又回溯了~Find out and fix it. >> >>>>>>>>>>Okey。小哥,怎么样了?哥们写得一手好字啊~ 这是修正后的代码: voidkmpNextEx(char *pattern, int *next, int len) { int i = 1; int j = -1; next[0]= -1; while(i < len) { if(j == -1 || pattern[i - 1] == pattern[j]) { /* 注意这里:如果发现与上一次匹配的值相同,则直接将上一次匹配的值赋予给新的 * next[i],这样可以改进如果Pattern有重复字符出现的情况 */ if(pattern[i - 1] != pattern[j - 1]) { next[i]= j + 1; }else { next[i]= next[j]; } ++j; ++i; } else { j= next[j]; } } } 图片 #include <stdio.h> #include <stdlib.h> #include <string.h> voidkmpNext(char*, int*, int); intkmpIndexOf(char*, char*); intbfIndexOf(char*, char*); int main(int argc, char*argv[]) { char *s1 = "2aaaaaaaaaaaaaaasdfasdf134123asdffffffo1asd1234\ ffffasdf213fvzazxcnvjklnaskld./zca;sdjkfjaiou21o3elan'[ \ 123454154sa4df6548210ykzht4341bwasd1231234239r \ 4sauioj9j91u8hdjkadu9891nkjklfau12 \ 134j0zhcjkvuiuizuionvjjksanfjih2bjkbmzjkxvhiannzjkvjkla \ 4=01293=0ykzht4341bwasd123123423l"; char *pat = "0ykzht4341bwasd123123423l"; char *answer = (char*)malloc(sizeof(pat) + 1); printf("Patter:\t%s\n", pat); printf("%-20s%d\n", "ByKMP:", kmpIndex(s1, pat)); strncpy(answer,s1 + kmpIndex(s1, pat), strlen(pat)); answer[strlen(pat)]= '\0'; printf("Answer:\t%s\n", answer); getchar(); return 0; } intkmpIndex(char *strsrc, char*pattern) { int *next = (int*)malloc(sizeof(int) *strlen(pattern)); int strsrcLen = strlen(strsrc); int patLen = strlen(pattern); int i = 0; int j = 0; kmpNext(pattern,next, strlen(pattern)); while(i < strsrcLen && j < patLen) { if(j == -1 || strsrc[i] == pattern[j]) { //printf("%d\n", i); ++i; ++j; } else { j= next[j] - 1; } } if(j >= patLen) { return i - patLen; } else { return -1; } } voidkmpNext(char *pattern, int*next, int len) { int i = 2; int j = 1; int count = 0; next[0]= 0; next[1]= 1; while(i < len) { j= 0; count= 0; while(pattern[j] == pattern[i - j - 1] && j< i - 1) { count++; ++j; } if(count == 0) { count= 1; } next[i]= count; ++i; } }
相关推荐
KMP算法
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
kmp算法,数据结构的实验报告,大学实验报告,希望能帮到大家
数据结构中KMP算法过程的Flash演示
kmp算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串...
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
KMP算法是对一般模式匹配算法的改进,由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。 对于一般的模式匹配算法:分别利用两个指针i和j指示主串S和T中的...
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
kmp算法的原理以及kmp算法的源代码
使用KMP算法实现模式匹配,包括next数组的求解,kmp算法的实现。关键代码有详细注释。
KMP算法的实现, 这程序代码是基于KMP算法来实现的,虽然很简单,但是可能也会对你有帮助的
利用KMP算法进行子串的快速查找,能够达到较高的速率