李大仁博客

[算法]两种字符串匹配算法（索引法，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 = 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 = 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=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
Exit mobile version