Home > 算法研究 > [算法]两种字符串匹配算法(索引法,KMP算法)对比,C语言实现

[算法]两种字符串匹配算法(索引法,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


索引法,就数最简单的字符串的匹配算法,原理就是,一个一个试,找到第一个以后,再看是否匹配第二个了,一直到字符串末尾,很经典的算法。

下面我们作个简单对比,看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#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){
 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) &#038;& (j < plen)){
 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) &#038;& (j < plen)){
 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++最近不怎么使用了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
KMP算法查找串S中含串P的个数count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
 
inline void NEXT(const string&#038; T,vector<int>&#038; next)
{
    //按模式串生成vector,next(T.size())
    next[0]=-1;
    for(int i=1;i<t.size();i++ ){
        int j=next[i-1];
        while(T[i]!=T[j+1]&#038;& 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&#038;  S,
                    const string&#038;  T)
{
    //利用模式串T的next函数求T在主串S中的个数count的KMP算法
    //其中T非空,
    vector<int> next(T.size());
    NEXT(T,next);
    string::size_type index,count=0;
    for(index=0;index<s.size();++index){
        int pos=0;
        string::size_type iter=index;
        while(pos<t.size() &#038;& iter<s.size()){
            if(S[iter]==T[pos]){
                ++iter;++pos;
            }
            else{
                if(pos==0)++iter;
                else pos=next[pos-1]+1;
            }
        }//while end
        if(pos==T.size()&#038;&(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<<count<<endl;
 
  system("PAUSE");
  return 0;
}
Categories: 算法研究 Tags: ,
  1. No comments yet.
  1. No trackbacks yet.