ch12 串

1. 基本概念

【子串】\(S.substr(i, k) = S[i, i+k) = S.prefix(i+k).suffix(k) = S.suffix(n-i).prefix(k)\)

【前缀】\(S.prefix(k) = S.substr(0, k) = S[0, k)\)

【后缀】\(S.suffix(k) = S.substr(n-k, k) = S[n-k, n)\)

2. KMP 算法

在任一时刻，都有 \(T[i-j,i) = P[0,j)\)，也就是说我们已经掌握 \(T[i-j,i)\) 的所有信息，一旦匹配失败，我们就应该已知哪些位置值得 / 对齐，而且下一轮中 \(T[i-j', i)\) 可径直接受，而不必再做比对。如此，\(i\) 将永远不必回退，比对成功，则与 \(j\) 同步前进一个字符，否则 \(j\) 更新为某更小的 \(t\)，并继续比对。

【查询表】\(t\) 不仅可以事先确定，而且仅根据 \(P[0,j) = T[i-j,i)\) 即可确定。视失败的位置 \(j\)，构造查询表 \(next[0,m)\)，一旦在 \(P[j]\) 处失配，只需将 \(j\) 替换为 \(next[j]\)，继续与 \(T[i]\) 比对。

【\(next\) 表】\(next[j+1] = next[j] + 1\) 当且仅当 \(P[j] = P[next[j]]\)。充分利用以往的比对所提供的信息，模式串快速右移，文本串无需回退。

C++

int *buildNext(char *P) {
    int m = strlen(P), j = 0;
    int *next = new int[m];

    int t = next[0] = -1;
    while (j < m-1) {
        if (t >= 0 || P[t] != P[j]) {   
            t = next[t];
        }
        else if (P[++t] != P[++j]) {
            next[j] = t;
        }
        else { // P[next[t]] != P[t] == P[j]
            next[j] = next[t];
        }
    }

    return next;
}

int match(char *P, char *T) {
    int *next = buildNext(P);
    int n = (int)strlen(T), i = 0;
    int m = (int)strlen(P), j = 0;

    while (j < m && i < n) {
        if (j < 0 || T[i] == P[j]) {
            i++; j++;
        }
        else {
            j = next[j];
        }
    }

    delete[] next;
    return i - j;
}

3. BM_BC 算法

【预处理】根据模式串 \(P\)，预先构造 \(bc[]\) 表以及 \(gs[]\) 表，与 \(next[]\) 类似，为日后的局部适配提供快速处置的建议。

【迭代】自右向左依次比对字符，找到极大的匹配后缀，若完全匹配，则返回位置；否则查表确定 \(P\) 右移的适当位置，并重新自右向左比对。

C++

// 画家算法
int *buildBC(char *P) {
    int *bc = new int[256];
    for (size_t j = 0; j < 256; j++) bc[j] = -1;

    for (size_t m = strlen(P), j = 0; j < m; j++)
            bc[P[j]] = j;

    return bc;
}

int match(char *P, char *T) {
    int *bc = buildBC(P);
    int n = (int)strlen(T), i;
    int m = (int)strlen(P), j;

    for (i = 0; i+m <= n; i += max(1, j - bc[T[i+j]])) {
        for (j = m-1; 0 <= j && P[j] == T[i+j]; j--) {
            if (j < 0) break;
        }
    }

    delete[] bc;
    return i;
}