字符串-我寄愁心与明月

字符串

KMP

    // 在主串 B 中匹配模式串 A

    // init
    fail[1] = j = 0;
    for (i = 2; i <= len_A; ++i) {
        while (j && A[j + 1] != A[i])
            j = fail[j];
        if (A[j + 1] == A[i])
            ++j;
        fail[i] = j;
    }

    // match
    j = 0;
    for (i = 1; i <= len_B; ++i) {
        while (j && A[j + 1] != B[i])
            j = fail[j];
        if (A[j + 1] == B[i]) {
            ++j;
            if (j == len_A) {
                Pos[++Pos_cnt] = i;
                j = fail[j];
            }
        }
    }

Manacher

初始化时在相邻两个字符以及字符串首位加特殊字符，然后最左和最右再添加两个不同的字符（ while (A[i - R[i]] == A[i + R[i]]) 的时候就不需要判边界了）。

一个长度 (n) 的字符串本质不同的回文串至多 (n) 个。

    int mx = 0, p = 0;

    // mx   最右端点 +1 位置
    // p    对应的回文中点
    for (int i = 1; i <= N; ++i) {
        R[i] = i < mx ? min(R[2 * pos - i], mx - i) : 1;
        while (A[i - R[i]] == A[i + R[i]])
            ++R[i];
        if (mx < i + R[i])
            pos = i, mx = i + R[i];
    }

Suffix Automaton

• Right/ Endpos
• Longest/ Max & Shortest/ Min
• 两个状态要么是包含关系，要么无交集。
• 求拓扑序等同于对 Mx 排序。
• 求 Right 集合大小：新加点时 V[x] = 1 ，拆出来的新点权值为零，拓扑排序之后 V[Par[x]] += V[x] 。
• 求 Right 集合元素：类似求大小，拓扑排序之后更新父亲，用数据结构去合并。新加点时 V[x] = 1, Right[x].insert(Tot) （ Tot 是这时主串总长度）。
• 空间足够就直接开 Nxt[_N][26] ， map 实测很慢容易 TLE 。
• 最长公共后缀在两个状态 Par 树的 LCA 上。

void extend(int t)
{
    int p = Lst, np = Lst = ++Tot;
    Mx[np] = Mx[p] + 1;
    Siz[np] = 1;
    while (p && !Nxt[p][t])
        Nxt[p][t] = np, p = Par[p];
    if (!p) {
        Par[np] = 1;
    } else {
        int q = Nxt[p][t];
        if (Mx[q] == Mx[p] + 1) {
            Par[np] = q;
        } else {
            int nq = ++Tot;
            Mx[nq] = Mx[p] + 1;
            copy(Nxt[q], Nxt[q] + 26, Nxt[nq]);
            Par[nq] = Par[q];
            Par[q] = Par[np] = nq;
            while (p && Nxt[p][t] == q)
                Nxt[p][t] = nq, p = Par[p];
        }
    }
    return;
}

void init()
{
    Mx[Lst = Tot = 1] = 0;
    return;
}