字符串模式匹配的三个算法

brilon

作者：飞阳（brilon）。转载请注明出处，谢谢。
[url]http://hi.baidu.com/burtcn[/url]

下面几个例子都是根据几个著名的字符串匹配算法的思想写的。。欢迎讨论。。

最朴素的模式匹配，是用蛮力的。。

#include <stdio.h>
#include <string.h>
int index(char a[],char b[],int pos){
             int i,j,alen,blen;
             i=pos;
             j=0;
             alen=strlen(a);
             blen=strlen(b);
             while(i<alen&&j<blen){
                       if(a[i]==b[j]){
                                 i++;
                                 j++;
                       }else{
                                 /*假设上一次是从下标p开始字符串匹配的*/
                                 /*要是发现后面的无法匹配，就从p+1处开始匹配*/         
                                 i=i-j+1;
                                 j=0;
                       }
             }
             /*判断j下标，如果b数组全部被比较完的话,j应该等于blen*/
             if(j>=blen)
                       return i-blen;
             else
                       return -1;         
}
int main(){
             char *a="abcburt";
             char *b="burt";
             printf("%d\n",index(a,b,0));
             return 0;
}

KMP算法

#include <stdio.h>
#include <string.h>
void setNext(char pattern[],int next[],int size){         
            int j;
            next[0]=-1;
            for(int i=1;i<size;i++){                    
                      for(j=next[i-1];j>=0&&pattern[i]!=pattern[j+1];j=next[j]);                    
                      next[i]=(j<0&&pattern[i]!=pattern[j+1])?-1:j+1;
            }
}
int match(char source[],char pattern[]){         
            int psize=strlen(pattern);         
            int *next=new int[psize];
            setNext(pattern,next,psize);         
            int i,j;
            int size=strlen(source);
            for(i=0,j=0;i<size;){                    
                      if(source[i]!=pattern[j]){                              
                                if(j>0){                                       
                                          j=next[j-1]+1;
                                }else
                                          i++;
                      }else
                                i++,j++;
                      if(j>=psize) break;
            }         
            return j>=psize?i-psize:-1;
}
int main(){         
            char *source="ababababeababcabdaf";
            char *pattern="ababc";
            printf("%d\n",match(source,pattern));         
            return 0;
}


BM算法。。

#include <stdio.h>
#include <string.h>
void getJump(int code[],char pattern[]){
           int len=strlen(pattern);
           for(int i=1;i<256;i++)
                     code[i]=len;
           for(i=0;i<len;i++)
                     code[(int)pattern[i]]=len-i-1;
}
int bmmatch(char text[],char pattern[]){
           int code[256];
           getJump(code,pattern);
           int tlen=strlen(text);
           int plen=strlen(pattern);
           int j,k;
           for(int i=plen-1;i<tlen;){                    
                     for(j=i,k=plen-1;k>=0&&text[j]==pattern[k];j--,k--);
                     if(k<0)
                               return j+1;
                     else
                               i+=code[text[j]];
           }
           return -1;         
}
int main(){
           char *t="the url is [url]http://hi.baidu.com/burtcn[/url]";
           char *p="burt";
           printf("%d\n",bmmatch(t,p));
           return 0;
}

[[i] 本帖最后由 brilon 于 2007-5-17 19:35 编辑 [/i]]

iptton

数据结构书上就有....

那个 setIndex　还有个优化的算法

brilon

是setNext。。

只要模式字符串是固定的，获得的next数组就是唯一的吧。。你说的优化是指怎么求next数组的优化吗？。。你怎么知道是优化的。。