[算法]两种字符串匹配算法（索引法，KMP算法）对比，C语言实现

今天做了个一个简单的字符对比程序，功能是实现从A串删除包含B最多的字符的操作，比如A=“aaaaabbbbbbabababa” B=“aaccbaab”，应当删除“aab”的，不是aa，相信知道搜索引擎的朋友肯定是知道的吧，这种算法主要用于去除页面中无效的关键字，来减少收录的计算消耗的一种方法，好了，具体算法明天拿出来吧，不过今天要讲的是两种比较常用的字符串匹配算法，KMP算法，索引法 KMP算法 是Knuth, Morris, Pratt三位前人提出的字符串快速匹配算法，简称KMP算法，典的算法了，还有以后发展的BM 和AB-BM算法，别急啊，这个下次再讲，最近是没时间写博客了，原理很简单，就是使用了额外的数值记录索引匹配的次数，然后根据这个结果进行结果计算的方法，不知道？可以参阅 http://www.chinaitpower.com/A/2003-01-04/45995.html 索引法，就数最简单的字符串的匹配算法，原理就是，一个一个试，找到第一个以后，再看是否匹配第二个了，一直到字符串末尾，很经典的算法。 下面我们作个简单对比，看代码： #include "stdio.h"#include "string.h"#include "stdlib.h"/*getnext*/void getNext(char p[],int next[]){int i, j, slen;slen = strlen(p);i = 0;j = -1;next[0] = -1;while(i < slen br> if((j == -1) || (p[i] == p[j])){ i++; j++; next[i] = j; }/*if*/ else{ j = next[j]; }/*else*/ }/*while*/}/*get_next*/int kmp(char s[], char p[], int pos, int next[]) {/*KMP算法*/int i, j, slen, plen;i = pos;j = 0;slen = strlen(s);plen = strlen(p);while((i < slen j plenbr> if((j == -1) || (s[i] == p[j])){ i++; j++; } else { j = next[j]; } }/*while*/if(j >= plen) { return (i-plen); }/*if*/else { return -1; }/*else*/}/*kmp*/int index(char s[], char p[], int pos){/*索引匹配法*/int i, j, slen, plen;i = pos;j = 0;slen = strlen(s);plen = strlen(p);while((i < slen j plenbr> if((s[i] == p[j])){ i++; j++; }/*if*/ else{ i = i-j+1; j = 0; }/*else*/}/*while*/if(j >= plen) { return (i-plen); }else { return -1; }}/*index*/void main(){char s[] = "acbaabcaacabaabaabcacaabc"; /*测试字符串*/char p[] = "abaabca";int next[50];getNext(p, next);printf("found index at %dn", kmp(s, p, 0, next));printf("found index at %dn", index(s, p, 0));}/*main*/ KMP算法是kmp()这个函数，INDEX算法是index()函数，相信诸位看出来了吧，KMP要多一个计算数组的，这也是精髓所在，也是效率所在，提高了一个数量级，诸位知道这样提高效率的结果了吧，不过，最坏的情况可能要浪费N多的空间了，好了，算法提供完，算法部分大家要是不懂的话，可以直接留言，或者跟我联系 附：来自网络的KMP匹配算法C++实现算法, 源自 http://www.chinaitpower.com/A/2003-01-04/45995.html，作者莫怪，借用一下给大家参考，个人比较喜欢纯C，C++最近不怎么使用了 KMP算法查找串S中含串P的个数count#include #include #include using namespace std; inline void NEXT(const string& T,vector & next) { //按模式串生成vector,next(T.size()) next[0]=-1; for(int i=1;i int j=next[i-1]; while(T[i]!=T[j+1]&& j>=0 ) j=next[j] ; //递推计算 if(T[i]==T[j+1])next[i]=j+1; else next[i]=0; // } } inline string::size_type COUNT_KMP(const string& S, const string& T) { //利用模式串T的next函数求T在主串S中的个数count的KMP算法 //其中T非空， vector next(T.size()); NEXT(T,next); string::size_type index,count=0; for(index=0;index int pos=0; string::size_type iter=index; while(pos if(S[iter]==T[pos]){ ++iter;++pos; } else{ if(pos==0)++iter; else pos=next[pos-1]+1; } }//while end if(pos==T.size()&&(iter-index)==T.size())++count; } //for end return count;}int main(int argc, char *argv[]){ string S="abaabcacabaabcacabaabcacabaabcacabaabcac"; string T="ab"; string::size_type count=COUNT_KMP(S,T); cout< < system("PAUSE"); return 0; } -------------------------------------------------------------------------------------- - 版权声明： - 如在本页面内无特别说明，本文内容均为[李大仁博客]原创，本文版权归[李大仁博客]所有。 - 欢迎转载，转载请务必在文章页面明显位置提供原文链接并注明出处。欢迎您在转载本文时保留本段声明。 - 文章标题： C语言实现的两种字符串匹配算法包括索引法，KMP算法 - 独立博客： 李大仁博客 - 永久链接：http://www.lidaren.com/archives/226 -------------------------------------------------------------------------------------- 以上内容由博客自动发布工具自动发布，最终显示内容和效果会与原文内容有所偏差，敬请谅解。