原理:
字符串查找算法中,最著名的两个是KMP算法和BM算法。两个算法在最坏情况下均具有线性的查找时间。但是在实际应用中,KMP算法并不比最简单的C库函数strstr()快多少,而BM算法则往往比KMP算法快上3-5倍。下面介绍一种比BM算法更快的查找算法——Sunday算法。
Sunday算法思想和BM算法类似,只不过Sunday算法是从前往后匹配,在匹配失败时关注的是:源串中参与匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过,移动步长=匹配串长度+1;否则,其移动步长=匹配串中最右端的该字符到末尾的距离+1。
#include <iostream> #include <string.h> using namespace std; int * getStep(char *a, char *b){ int *step = new int[256]; for (int i=0;i<256;i++){ step[i]=strlen(b)+1; } int sublen = strlen(b); for (int i=0;i<sublen;i++){ step[b[i]]=sublen-i; } return step; } int sundaySearch(char *mainstr, char *substr, int *step){ int i=0,j=0; int mainlen=strlen(mainstr); int sublen=strlen(substr); while (i<mainlen){ int temp = i; while (j<sublen){ if (mainstr[i]==substr[j]){ i++; j++; continue; } else { i = temp + step[mainstr[temp+sublen]]; if (i+sublen>mainlen) return -1; j=0; break; } } if (j==sublen) return temp; } } int main(){ char a[]="LESSONS TEARNED IN SOFTWARE TE"; char b[]="SOFTWARE"; int * step = getStep(a,b); cout << sundaySearch(a,b,step); }