Sunday算法详解

概述

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的基本原理和使用。如有问题，欢迎指正。