字符串匹配算法—

处理字符串的过程中，难免会遇到字符匹配的问题。常用的字符匹配方法

1. 朴素模式匹配算法(Brute-Force算法)

求子串位置的定位函数Index( S, T, pos).

　　模式匹配：子串的定位操作通常称作串的模式匹配。

　　目标串：主串S。

　　模式串：子串T。

　　匹配成功：若存在T的每个字符依次和S中的一个连续字符序列相等，则称匹配成功。返回T中第一个字符在S中的位置。

　　匹配不成功：返回0。

　　lBrute-Force简称为BF算法,亦称简单匹配算法,其基本思路是:

从目标串s=“s1s2…sn"的第一个字符开始和模式串t=“t1t2…tm"中的第一个字符比较,若相等,则继续逐个比较后续字符；

　　否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。

　　依次类推,若从模式串s的第i个字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回0。

2. 模式匹配的改进算法-KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。

　　每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离，继续进行比较。

　　定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。(具体描述参见数据结构（严蔚敏版）)

　　next函数的定义：

下面给出实现：

　　其中获取next数组的函数，和课本描述稍微有点差异。原文使用字符串第一个值表示字符串的大小，真正的字符串内容从第二个字符开始，和平时使用不一致，本文将其改变。并对next数组的值的意义进行改变，认为next值为-1时，匹配失效，需要改变主串的比较的数组（i+1），即相对于课本，把所有next值减一，而意义不变。

 #include <cstdio>

 #include <string>

 using namespace std;

 void get_next(string p, int* next)

 {

     int sp = p.size();

     next[]=-;

     int i,j;

     i=;j=-;

     while(i<sp-)

     {

         if(j==-||p[i]==p[j])

         {

             ++i;++j;

             if(p[i]!=p[j])

                 next[i]=j;

             else

                 next[i]= next[j];

         }

         else

         {

             j=next[j];

         }

     }

 }

 void printNext(int* next,int n)

 {

     for(int i =; i<n;i++)

         printf("%d ",next[i]);

     printf("\n");

 }

 int kmp_search(string s, string pattern,int pos)

 {

     int sizeP = pattern.size();

     int sizeS = s.size();

     int *next = new int[sizeP];

     memset(next,,sizeof(int)*sizeP);

     get_next(pattern,next);

     printNext(next,sizeP);

     int i,j;

     i=;j=;

     while(i<sizeS&&j<sizeP)

     {

         if(j==-||s[i]==pattern[j])

         {

             ++i;++j;

         }

         else

         {

             j=next[j];

         }

     }

     delete next;

     if(j==sizeP)

     {

         return i-sizeP;

     }

     else

         return -;

 }

 int main()

 {

     string s = "abacaesabacadfabacawersdf";

     string pat = "abacaw";

     int result = kmp_search(s,pat,);

     printf("s: %s\tt: %s\npos: %d\n",s.c_str(),pat.c_str(),result);

     return ;

 }

巴特西

字符串匹配算法——KMP算法

最新文章

热门文章