字符串匹配 – Shift-And算法

The Shift-AND algorithm is similar to KMP and Z-algorithm, it inputs a pattern P and a long text T, outputs in linear time all occurrences of P in T. While KMP only maintains the longest prefix of P that is also a suffix of the examining prefix of T, Shift-AND keeps track of all prefixes of P that match any suffixes of the examining prefix of T. 

Shift-And算法不仅可以处理单模匹配问题，还可以处理每个位置允许有多种字符匹配的场景，如正则(a|b|c)&(d|e)&(f|g).

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

int GetNextP(char ch, int *code, int p) { 
    // p << 1  表示随着文本串增加1位 有可能匹配成功前几位  
    // 例如：before能匹配前2位与前4位 那么after可能 匹配前3位与前5位

    // |1 表示随着文本串增加1位 是有可能 匹配成功前1位（第1位）的
    // 例如：此时文本串可能 匹配模式串的前1位、前3位、前5位
    // 即假设：文本串能匹配模式串的前1位、前3位、前5位

    // &code[ch] 用来确认‘假设‘的正确性
    // 例如：看ch这个字符是否在模式串的第1位、第3位、第5位出现过，
    // 将ch在模式串中出现过的位，p对应位 置为1，没出现过的位 p对应位 置为0
    return (p << 1 | 1) & code[ch];  
}
/**
 * @brief Shift-And 时间复杂度O(n) 
 *        将模式串处理成另外一种信息格式code[]（兼容性特别强） code[i]使用二进制表示pattern[n]可以出现在第几位
 *        适用于流数据处理 比kmp算法更高效
 *        适合处理每个位置可以有多种字符匹配的场景 如这种形式的正则表达式模式串：(a|c|d)&e&(a|b|c)&(d|f)
 * @param text 
 * @param pattern 
 * @return int ：pattern在text中匹配成功的起始位置
 */
int shift_and(const char *text, const char *pattern) { 
    int code[256] = {0}; 
    int n = 0; 
    // code: int数组 记录模式串中每种字符 都在模式串的第几位出现过
    // 二进制的第n位为1 代表pattern[n]在pattern的第n位出现过
    for (n = 0; pattern[n]; ++n) code[pattern[n]] |= (1 << n); 
    // P：表示截止文本串当前索引位置i为止 能够匹配成功模式串的前几位
    // 二进制的第n位值为1 代表可以匹配成功模式串的前n位
    int p = 0; 
    for (int i = 0; text[i]; i++) { 
        p = GetNextP(text[i], code, p); // 完美诠释了自动机的思想
        // p的第n-1位为1，表示整个模式串匹配到了
        if (p & (1 << (n - 1))) return i - n + 1; 
    }
    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(shift_and, s1, s2); 
    }
    return 0; 
}