概述
Sunday是一种字符串匹配算法。以其优秀的性能和较低的复杂度，饱受好评。
原理
Sunday
现在要在主串”applapplepie”中查找模式串”apple”。设主串长度为n，模式串长度为m。模式串第一位在主串中的索引为s。
假定我们得到了一个神奇的HashMap<char,int>叫shift，它具有这样的性质。当我们匹配失败时，我们取主串s+m的值x。
然后，我们取得j = shift.get(x)。
最后，我们把原先的s向后移j位，再进行匹配。如此反复，就能非常高效的找到模式串的位置。
下面是一个例子中，我直接给出了这个神奇的shift。在这个shift的帮助下，我们只进行了三次匹配，就找到了正确的匹配。
// --- shift ---
// a:5
// p:3
// l:2
// e:1
// a p p l a p p l e p i e
// a p p l e
匹配失败 末位的下一位为p
shift = 3
// a p p l a p p l e p i e
// a p p l e
匹配失败 末位的下一位为e
shift = 1
// a p p l a p p l e p i e
// a p p l e
匹配成功
所以在shift已知的情况下，Sunday算法如下：
const int maxNum = 1005;
int shift[maxNum];
int Sunday(const string& T, const string& P) {
int n = T.length();
int m = P.length();
// 模式串开始位置在主串的哪里
int s = 0;
// 模式串已经匹配到的位置
int j;
while(s <= n - m) {
j = 0;
while(T[s + j] == P[j]) {
j++;
// 匹配成功
if(j >= m) {
return s;
}
}
// 找到主串中当前跟模式串匹配的最末字符的下一个字符
// 在模式串中出现最后的位置
// 所需要从(模式串末尾+1)移动到该位置的步数
s += shift[T[s + m]];
}
return -1;
}
shift
上面看到，其实如果我们已知shift，模式串匹配的过程就非常容易了。
所以接下来，我们来看一看shift的获取方式。
// 默认值，移动m+1位
for(int i = 0; i < maxNum; i++) {
shift[i] = m + 1;
}
// 模式串P中每个字母出现的最后的下标
// 所对应的主串参与匹配的最末位字符的下一位字符移动到该位，所需要的移动位数
for(int i = 0; i < m; i++) {
shift[P[i]] = m - i;
}
这里有两个for循环。第一个for循环表示：如果一个字符，没有在我们的模式串中出现过。当它出现在我们的s+m位置上时，我们可以直接跳过它了。
此时
s += shift[T[s + m]];
会变成：
s += m + 1;
非常合理〜
如果s+m位置上的字符在模式串中出现过呢？我们就应该赶紧让模式串跳到这个匹配的位置上，然后，遍历模式串，确认其是否整体匹配。
所以，每一个字符对应跳几位，是由其在模式串中的位置决定的。
附上整体代码：
const int maxNum = 1005;
int shift[maxNum];
int Sunday(const string& T, const string& P) {
int n = T.length();
int m = P.length();
// 默认值，移动m+1位
for(int i = 0; i < maxNum; i++) {
shift[i] = m + 1;
}
// 模式串P中每个字母出现的最后的下标
// 所对应的主串参与匹配的最末位字符的下一位字符移动到该位，所需要的移动位数
for(int i = 0; i < m; i++) {
shift[P[i]] = m - i;
}
// 模式串开始位置在主串的哪里
int s = 0;
// 模式串已经匹配到的位置
int j;
while(s <= n - m) {
j = 0;
while(T[s + j] == P[j]) {
j++;
// 匹配成功
if(j >= m) {
return s;
}
}
// 找到主串中当前跟模式串匹配的最末字符的下一个字符
// 在模式串中出现最后的位置
// 所需要从(模式串末尾+1)移动到该位置的步数
s += shift[T[s + m]];
}
return -1;
}
复杂度
Sunday平均性能的时间复杂度为O(n)，最差情况的时间复杂度为O(n * m)，空间复杂度，则是主串和模式串的字符范围。
以上就是Sunday的基本原理和使用。如有问题，欢迎指正。
