字符串匹配 – Sunday算法

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。

——百度百科

黄金对齐点位：每次匹配时母串和模式串对齐的索引位置。

1. 先处理出每一种字符在模式串pattern中出现的最后位置last_pos；last_pos[i]默认为-1，如此在步骤4中，遇到一个pattern中没有的字符时，i可以向后跳m+1个位置。
2. 当前母串text要对比的尾部字符索引为i + m（母串的黄金对齐点位）；
3. 其在pattern中的黄金对齐点位是last_pos[text[i + m]]（字串的黄金对齐点位）；
4. text中于pattern进行黄金对齐点位对齐后，母串中的对比首索引i += m – last_pos[text[i + m]];
5. 轮询pattern进行匹配，匹配成功则return；
6. 匹配失败，则重复步骤4.

Sunday算法适合在文章中查找字符串，最快的时间复杂度可以达到O(n/m)。在实际应用场景中远远优于暴力匹配、KMP算法。

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <queue> 
#include <stack> 
#include <algorithm> 
#include <string> 
#include <map> 
#include <set> 
#include <vector> 
using namespace std; 

/**
 * @brief sunday算法
 *        最好的时间复杂度可以达到O(m/n) 适用于在文章中查找信息    m=text.length,n=pattern.length
 * @param text 文本串
 * @param pattern 模式串
 * @return int 
 */
int sunday(const char *text, const char *pattern) { 
    #define BASE 256 // 定义字符范围在256个  参考：ASCII字符编码范围是[0, 127]
    int n = strlen(text), m, last_pos[BASE]; //n 文本串长度，m 模式串长度，last_pos 字符在模式串中最后出现的位置
    for (int i = 0; i < BASE; i++) last_pos[i] = -1; //last_pos 默认-1
    for (m = 0; pattern[m]; ++m) last_pos[pattern[m]] = m; // 计算每个模式串字符在模式串中最后出现的位置
    // 遍历text，i + m <= n剪枝
    for (int i = 0; i + m <= n; i += (m - last_pos[text[i + m]])) { 
        // i += (m - last_pos[text[i + m]]) 根据黄金等位分割点text[i + m]在pattern中的last_pos 进行text和pattern的重新对齐 确定文本串中i得最新位置 
        int flag = 1; //flag 是否匹配
        for (int j = 0; pattern[j]; ++j) { 
            if (text[i + j] == pattern[j]) continue; //依次匹配文本串和模式串的每一位
            flag = 0; //匹配到不相等 匹配失败
            break; 
        }
        if (flag) return i; 
    }
    return -1; 
}

#define TEST(func, s1, s2) { \ printf("%s(\"%s\", \"%s\") = %d\n", #func, s1, s2, func(s1, s2)); \ }
    
int main() { 
    char s1[100], s2[100]; 
    while (cin >> s1 >> s2) { 
        TEST(sunday, s1, s2); 
    }
    return 0; 
}