数据结构：大整数实战，提升 Shift-And 算法能力

任务

如果给你一个文本串和模式串，让你查找文本串中是否包含模式串，你用程序怎么完成？

字符串匹配问题

在一个大的字符串里面，查找是否包含另外一个较小的字符串。

暴力法解决

用模式串的首字母依次和文本串中的每一位对齐，每次对齐以后，看看所对应区域是否匹配，如果匹配就说明文本串包含模式串。

// 暴力匹配算法程序
int bruce_force(const char *text, const char *p) {
    // 遍历文本串每一位
    for (int i = 0; text[i]; i++) {
        int flag = 1;
        // 从文本串的第 i 位开始与模式串进行匹配
        for (int j = 0; p[j]; j++) {
            if (text[i + j] == p[j]) continue;
            // 当代码到了这里，说明某一位不匹配
            flag = 0;
            break;
        }
        if (flag) return 1;
    }
    return 0;
}

时间复杂度是 O(nm)，其中，n 是文本串的长度，m 是模式串的长度。
如果文本串长度是 10，模式串长度是 3，那么这个程序差不多要计算 30 次，外层循环 10 次，内层循环每次循环 3 次。

效率比较差，放弃。

Shift-And 算法

基本流程：首先做信息的转换，然后利用位运算，完成单模匹配问题。

Shift-And 中的信息转换

利用位运算做匹配

我们假设模式串的长度是 m ，code(str[i]) 代表了文本串第 i 位字符的编码，整个匹配过程，从前往后，依次处理文本串的每一位，处理到第 i 位的时候，就是用第 i 位字符的编码（code（str[i])），与 p 左移 1 位并或上 1 以后的值（p<< 1 | 1），做“按位与”运算，把得到的值赋给 p 变量。最终，当 p 的二进制表示的第 m 位为 1 时，说明匹配成功了。

示例，当模式串为 cdd，文本串为 acdd 时候的匹配流程：

p 公式的理解与推导

其中 pm 代表 p 的二进制表示的第 m 位为 1，pm−1 表示 p 的二进制表示的第 m-1 位为 1。因为只有第 m-1 位为 1，才可能左移 1 位以后的结果第 m 位为 1。

实现Shift-And 算法

int shift_and(const char *str, const char *p_str) {
    int code[256] = {0}, m = 0;
    // 初始化每一个字符的编码
    for (int i = 0; p_str[i]; i++, m++) {
        code[p_str[i]] |= (1 << i);
    }
    int p = 0;
    for (int i = 0; str[i]; i++) {
        p = (p << 1 | 1) & code[str[i]];
        // 如果 p 所对应的模式串最高位为1，代表匹配成功
        if (p & (1 << (m - 1))) return 1;
    }
    return 0;
}

该算法只用了两次循环，一次循环是遍历模式串，生成编码 code 信息，第二次循环是遍历文本串 str，循环迭代得到 p 变量的值，直到 p 变量的第 m 位为 1 时，就代表匹配成功。
时间复杂度就是 O(n + m) 。意味着，同样是文本串 10000 的长度，模式串 1000 长度，Shift-And 算法，是暴力匹配算法效率的 1000 倍！

小结

等价信息表示对于解决问题很重要。