Sunday算法原理与实现（模式匹配）

xq8995209

      字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法则往往比KMP算法快上3－5倍。但是BM算法还不是最快的算法，这里介绍一种比BM算法更快一些的查找算法---Sunday算法。

   Sunday算法其实思想跟BM算法很相似，只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过，即移动步长= 匹配串长度+ 1；否则，同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。

具体源代码实现如下（源代码中已注明实现过程）：

#include<iostream>
#include<string.h>
using namespace std;
//一个字符8位 最大256种
#define MAX_CHAR_SIZE 256
#define MAXSIZE 100
/*
设定每个字符最右移动步长，保存每个字符的移动步长
如果大串中匹配字符的右侧一个字符没在子串中，大串移动步长=整个串的距离+1
如果大串中匹配范围内的右侧一个字符在子串中，大串移动距离=子串长度-这个字符在子串中的位置
*/
int *setCharStep(char *subStr)
{
int i;
     int *charStep=new int[MAX_CHAR_SIZE];
     int subStrLen=strlen(subStr);
     for(i=0;i<MAX_CHAR_SIZE;i++)
             charStep=subStrLen+1;
     //从左向右扫描一遍 保存子串中每个字符所需移动步长
     for(i=0;i<subStrLen;i++)
     {
            charStep[(unsigned char)subStr]=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<mainStrLen)
     {                  
            //保存大串每次开始匹配的起始位置，便于移动指针
             int tem=main_i;
             while(sub_j<subStrLen)
             {
                    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+=charStep[(unsigned char)firstRightChar];
                         sub_j=0;   
                         break;//退出本次失败匹配 重新一轮匹配
                    }  
             }
             if(sub_j == subStrLen)
                       return main_i-subStrLen;
     }
     return -1;
}


int main()
{
char mainStr[MAXSIZE];
char subStr[MAXSIZE];
int answer, i;
printf("\nBoyer-Moore String Searching Program");
printf("\n====================================");
printf("\n\nmainStr String --> ");
gets(mainStr);
printf( "\nsubStr String --> ");
gets(subStr);
int *charStep=setCharStep(subStr);
if ((answer = sundaySearch(mainStr,subStr,charStep)) >= 0)
{
  printf("\n");
  printf("%s\n", mainStr);
  for (i = 0; i < answer; i++)
   printf(" ");
  printf("%s", subStr);
  printf("\n\nPattern Found at location %d\n", answer);
}
else
  printf("\nPattern NOT FOUND.\n");
return 0；
}