Sunday-字符串匹配算法

听说这个算法比kmp效率还高，而且重要的是还好理解，所以就.....

好了，sunday算法还真的很好理解，用下面的例子来说明吧：

  j                                k

t

h

i

s

i

s

a

s

i

m

p

l

e

e

x

a

m

p

l

e

.

e

x

a

m

p

l

e

  i      

这个例子中上面的字符串是待查找字符串，下面的是子串。sunday的思想是这样的：

首先i,j两个指针指示的位置（也就是从头开始匹配），当发现失配的时候就判断子串的后一位在母串的字符（在上面的例子中是空格字符，k标记处）是否在子串中存在？如果存在则将该位置和子串中的该字符对齐，在从头开始匹配。如果不存在就将子串向后移动，和母串k+1处的字符对齐，再进行匹配。重复上面的操作直到找到，或母串被找完结束。

对于上面的例子继续进行，刚才说了失配，并且空格在子串中不存在，所以子串向后移动，子串的第一个字符和母串的k+1位置的字符对齐，如下图：

                                 j                                 k

t

h

i

s

i

s

a

s

i

m

p

l

e

e

x

a

m

p

l

e

.

e

x

a

m

p

l

e

                                 i

这次比较还是失配，但是k位置的e在子串中出现了，而且第一个就是，最后一个也是，这时候一定要将子串中靠后出现的e和母串中的e对齐如下图：

                                       j                               k

t

h

i

s

i

s

a

s

i

m

p

l

e

e

x

a

m

p

l

e

.

e

x

a

m

p

l

e

                                      i

为什么是最靠后的一个呢？如果这里用第一个e来和母串中的e对齐，就有可能将中间出现的可匹配字符串空过去。

同上这次还是失配，所以还要再进行一次。

t

h

i

s

i

s

a

s

i

m

p

l

e

e

x

a

m

p

l

e

.

e

x

a

m

p

l

e

这次就匹配成功了。

#include

#include

using namespace std;

//一个字符8位 最大256种

#define MAX_CHAR_SIZE 256

 

/*设定每个字符最右移动步长，保存每个字符的移动步长

如果大串中匹配字符的右侧一个字符没在子串中，大串移动步长= 整个串的距离+1

   如果大串中匹配范围内的右侧一个字符在子串中，大串移动距离= 子串长度 - 这个字符在子串中的位置

*/

int *setCharStep(char *subStr)

{

     int *charStep=new int[MAX_CHAR_SIZE];

     int subStrLen=strlen(subStr);

     for(int i=0;i

             charStep[i]=subStrLen+1;

     //从左向右扫描一遍 保存子串中每个字符所需移动步长

     for(int i=0;i

     {

            charStep[(unsigned char)subStr[i] ]=subStrLen-i;         

     }

     return charStep;

}

/*

   算法核心思想，从左向右匹配，遇到不匹配的看大串中匹配范围之外的右侧第一个字符在小串中的最右位置

   根据事先计算好的移动步长移动大串指针，直到匹配

*/

int sundaySearch(char *mainStr,char *subStr,int *charStep)

{

     int mainStrLen=strlen(mainStr);

     int subStrLen=strlen(subStr);

     int main_i=0;

     int sub_j=0;

     while(main_i

     {                  

            //保存大串每次开始匹配的起始位置，便于移动指针

             int tem=main_i;

             while(sub_j

             {

                    if(mainStr[main_i] ==   subStr[sub_j])

                    {

                            main_i++;

                            sub_j++;

                            continue;                   

                    }                

                    else{

                        //如果匹配范围外已经找不到右侧第一个字符，则匹配失败

                         if(tem+subStrLen > mainStrLen)

                                     return -1;

                         //否则 移动步长 重新匹配

                         char firstRightChar=mainStr[tem+subStrLen];

                         main_i =tem + charStep[(unsigned char)firstRightChar];

                         sub_j=0;   

                         break;//退出本次失败匹配 重新一轮匹配

                    }  

             }

             if(sub_j == subStrLen)

                       return main_i-subStrLen;

     }

     return -1;

}

int main()

{

         char *mainStr="absaddsasfasdfasdf";

         char *subStr="dd";

         int *charStep=setCharStep(subStr);

         cout<<"位置： "<

         system("pause");

         return 0;    

}