字符串匹配算法之Sunday算法
背景
我们第一次接触字符串匹配，想到的肯定是直接用2个循环来遍历，这样代码虽然简单，但时间复杂度却是Ω(m*n)，也就是达到了字符串匹配效率的下限。于是后来人经过研究，构造出了著名的KMP算法（Knuth-Morris-Pratt算法），让我们的时间复杂度降低到了O(m+n)，但现代文字处理器中，却很少使用KMP算法来做字符串匹配，因为还是太慢了。现在主流的算法是BM算法（Boyer-Moore算法），成功让平均时间复杂度降低到了O(m/n)，而Sunday算法，则是对BM算法的进一步小幅优化。
KMP算法很多人看了一遍遍以后，对next[n]数组的理解还是有点困难（包括笔者），写代码的时候总是容易变成这种情况（/捂脸.jpg）：
（切到网页）：马冬梅
（切到编译器）：马什么梅
（切到网页）：马冬梅
（切到编译器）：马冬什么
（切到网页）：马冬梅
（切到编译器）：什么冬梅
而Sunday算法，理解起来则是非常容易，同时极低的时间复杂度，让Sunday算法成为了笔者目前最常使用的字符串匹配算法
算法解释
Sunday算法和BM算法稍有不同的是，Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。
- 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；
- 否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。
下面举个例子说明下Sunday算法。假定现在要在主串”substring searching”中查找模式串”search”。
-
刚开始时，把模式串与文主串左边对齐：
Sunday算法1
- 结果发现在第2个字符处发现不匹配，不匹配时关注主串中参加匹配的最末位字符的下一位字符，即标粗的字符
i，因为模式串search中并不存在i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从i之后的那个字符（即字符n）开始下一步的匹配，如下图：
Sunday2
-
结果第一个字符就不匹配，再看主串中参加匹配的最末位字符的下一位字符，是’r’，它出现在模式串中的倒数第3位，于是把模式串向右移动3位（m - 3 = 6 - 3 = r 到模式串末尾的距离 + 1 = 2 + 1 =3），使两个’r’对齐，如下：
Sunday3
- 匹配成功。
详细代码（Java版）
static final int ASCII_SIZE = 126;
int sunday(char[] total,char[] part){
int tSize = total.length;
int pSize = part.length;
int[] move = new int[ASCII_SIZE];
//主串参与匹配最末位字符移动到该位需要移动的位数
for (int i= 0;i<ASCII_SIZE;i++){
move[i] = pSize+1;
}
for (int i = 0;i<pSize;i++){
move[part[i]] = pSize-i;
}
int s = 0;//模式串头部在字符串位置
int j;//模式串已经匹配了的长度
while(s<=tSize-pSize){//到达末尾之前
j = 0;
while(total[s+j]==part[j]){
j++;
if (j>=pSize){
return s;
}
}
s+=move[total[s+pSize]];
}
return -1;
}
我们来一步一步解释
int sunday(char[] total,char[] part){
int tSize = total.length;
int pSize = part.length;
...
}
其中total为主串，part为模式串
int[] move = new int[ASCII_SIZE];
//主串参与匹配最末位字符移动到该位需要移动的位数
for (int i= 0;i<ASCII_SIZE;i++){
move[i] = pSize+1;
}
for (int i = 0;i<pSize;i++){
move[part[i]] = pSize-i;
}
定义一个长为ASCII码长度大小的数组，用于存放存入匹配失败时模式串需要移动的长度。这里看到，除了part中不存在的字符，移动长度都直接是模式串长度+1；而part中存在的字符，则需要移动的长度则依次减小。这也很好理解，因为我们匹配的是模式串首部位置+模式串长度+1位置的字母存在于模式串中的位置，这个位置越靠后，则整个模式串需要移动的距离就越短
int s = 0;//模式串头部在字符串位置
int j;//模式串已经匹配了的长度
s为模式串首部在字符串的位置，一开始为0；j是模式串已经匹配了的长度，一开始也是0
while(s<=tSize-pSize){ // 1
j = 0; // 2
while(total[s+j]==part[j]){// 3
j++;// 4
if (j>=pSize){
return s;// 5
}
}
s+=move[total[s+pSize]]; // 6
}
这里是最关键的代码了，咱们讲细一点
-
首先循环继续的判定条件为
s<=tSize-pSize，s作为模式串首部在字符串的位置，加上pSize肯定要比tSize小，不然就越界了 -
j是模式串已经匹配了的长度，匹配开始或者匹配失败后都要给j赋值为0，重新开始计数 -
接下就是一个字符一个字符的比较的循环
-
已经比较成功，则
j加1 -
如果
j已经大于等于pSize，就返回模式串首部在字符串当前的位置 -
这是最关键的一句，涉及到Sunday算法的核心，也就是模式串在主串中的“跳跃”，我们把这句代码分解一下就好理解的多
int nextCompare = s+pSize; //跳到s+pSize，也就是模式串后的一个字符的位置 int ascii_number = total[nextCompare];//获取转跳后位置的字符的ascii码值 int moveLength = move[ascii_number];//根据ascii码值在move数组中查找模式串需要跳跃的长度 s += moveLength; //让模式串首部在字符串的位置加上跳跃的长度，完成跳跃
一个例子
String str1 = "searching substring";
String str2 = "substr";
sunday(str1.toCharArray(),str2.toCharArray());
其实最关键的，就是要计算move[]数组中的各个值，我们来手动算一下
pSize = 6;
i = 0 : part[i] = s; move[s] = 6;
i = 1 : part[i] = u; move[u] = 5;
i = 2 : part[i] = b; move[b] = 4;
i = 3 : part[i] = s; move[s] = 3;
i = 4 : part[i] = t; move[t] = 2;
i = 5 : part[i] = r; move[r] = 1;
final:
move[s] = 3，
move[u] = 5,
move[b] = 4,
move[s] = 3，
move[t] = 2,
move[r] = 1 ,
move[其他] = 7
然后进行匹配
-
s = 0, j = 1时，匹配失败total[s+pSize]=total[6]=imove[i]= 7s+=7待匹配串为
ing substring -
s = 7 , j = 0 时，匹配失败total[s+pSize]=total[13]=umove[u]= 5s+=5待匹配串为
substring -
匹配成功
Sunday算法的缺点
看上去简单高效非常美好的Sunday算法，也有一些缺点。因为Sunday算法的核心依赖于move数组，而move数组的值则取决于模式串，那么就可能存在模式串构造出很差的move数组。例如下面一个例子
主串：baaaabaaaabaaaabaaaa
模式串：aaaaa
这个模式串使得move[a]的值为1，即每次匹配失败时，只让模式串向后移动一位再进行匹配。这样就让Sunday算法的时间复杂度飙升到了O(m*n)，也就是字符串匹配的最坏情况
总结
当然，也不能因为存在最坏的情况就直接否定Sunday算法，大多数情况下，Sunday依然是一个简单高效的算法，值得我们熟练学习掌握。
网友评论