论坛 › 【编程】编程圣殿 › 字符串模式匹配的三个算法

brilon 发表于 2007-5-15 15:10

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

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

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

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

#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==b){
                                 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=-1;
            for(int i=1;i<size;i++){                  
                      for(j=next;j>=0&&pattern!=pattern;j=next);                  
                      next=(j<0&&pattern!=pattern)?-1:j+1;
            }
}
int match(char source[],char pattern[]){         
            int psize=strlen(pattern);         
            int *next=new int;
            setNext(pattern,next,psize);         
            int i,j;
            int size=strlen(source);
            for(i=0,j=0;i<size;){                  
                      if(source!=pattern){                              
                              if(j>0){                                       
                                          j=next+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=len;
         for(i=0;i<len;i++)
                     code[(int)pattern]=len-i-1;
}
int bmmatch(char text[],char pattern[]){
         int code;
         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==pattern;j--,k--);
                     if(k<0)
                               return j+1;
                     else
                               i+=code];
         }
         return -1;         
}
int main(){
         char *t="the url is http://hi.baidu.com/burtcn";
         char *p="burt";
         printf("%d\n",bmmatch(t,p));
         return 0;
}

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

iptton 发表于 2007-5-15 16:52

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

那个 setIndex　还有个优化的算法

brilon 发表于 2007-5-17 19:28

是setNext。。

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

查看完整版本: 字符串模式匹配的三个算法