字符串匹配算法Sunday

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
一种字符串匹配算法，时间复杂度为O(n)。

Sunday算法在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。

  • 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；
  • 否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。

偏移表

在预处理中，计算偏移表。 $$ shift[w] = \begin{cases} m - max{i < m | P[i] = w} & \mbox{ if } w \mbox{ is in } P[0..m-1] \ m + 1 & \mbox{ otherwise } \end{cases} $$

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int charnum = 1005;
int shift[charnum];
int Sunday(const string& T, const string& P) {
    int n = T.length();
    int m = P.length();
    for(int i = 0; i < charnum; i++) {
        shift[i] = m + 1; 
    }
    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; 
            } 
        }
        s += shift[T[s + m]];
    } 
    return -1; 
}