KMP

　　求border

for (int i = 2, j = 0; i <= m; i++)
{
    while (b[i] != b[j + 1] && j) j = nex[j];
    if (b[i] == b[j + 1]) j++;
    nex[i] = j;
}

AC自动机    自动AC的机器 

　　相当于$KMP+Trie$，用于求多个模式串的匹配

//构造 
inline void ACbuild()
{
    queue<int> que;
    for (int i = 0; i < 26; i++) if (trie[0][i]) que.push(trie[0][i]);
    while (que.size())
    {
        int u = que.front();
        que.pop();
        for (int i = 0; i < 26; i++)
        {
            if (trie[u][i])
            {
                last[trie[u][i]] = trie[last[u]][i];
                que.push(trie[u][i]);
            }
            else trie[u][i] = trie[last[u]][i];
        }
    }
}

 

后缀数组 SA

　　将字符串的$1\leq i\leq n,s[i,n]$按照从小到大排序，用倍增和计数排序

　　$O(nlogn)$

//rk[i]表示s[i,n]的排名，sa[i]表示排名是i的子串的首字符位置
inline void sort_SA(int w)
{
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++) id[i] = sa[i];
    for (int i = 1; i <= n; i++) cnt[rk[id[i] + w]]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i; i--) sa[cnt[rk[id[i] + w]]--] = id[i];
}

int main()
{
    scanf("%s", str + 1);

    n = strlen(str + 1);
    m = max(n, 300);
    for (int i = 1; i <= n; i++) cnt[rk[i] = str[i]]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i; i--) sa[cnt[rk[i]]--] = i;

    for (int w = 1; w < n; w <<= 1)
    {
        sort_SA(w);
        sort_SA(0);
        memcpy(last, rk, sizeof(rk));
        for (int p = 0, i = 1; i <= n; i++)
        {
            if (last[sa[i]] == last[sa[i - 1]] && last[sa[i] + w] == last[sa[i - 1] + w]) rk[sa[i]] = p;
            else rk[sa[i]] = ++p;
        }
    }
}

　　用途：

　　寻找最小的循环移动位置，例题[JSOI2007]字符加密

　　在主串T中在线寻找模式串S，将T后缀数组排序后在里面二分查找S

　　从字符串首尾提取字符最小化字典序，例题[USACO07DEC] Best Cow Line

Manacher 马拉车

　　计算$str$中最长回文子串的长度

　　$d1[i]$表示以$i$为中心的长度为奇数的回文子串的半径，$d2[i]$表示$i$为中心的长度为偶数的回文子串的半径

　　例：下标以$1$开始的$str=[a,b,c,b,b,c]$中，$d1[3]=2:[b,c,b]$，$d2[5]=2:[c,b,b,c]$

for (int l = 1, r = -1, i = 1; i <= n; i++)
{
    int k = i > r ? 1 : min(d1[l + r - i], r - i);
    while (0 < i - k && i + k <= n && str[i - k] == str[i + k]) k++;
    d1[i] = k--;
    if (i + k > r) l = i - k, r = i + k;
    ans = max(ans, (d1[i] - 1) * 2 + 1);
}
for (int l = 1, r = -1, i = 1; i <= n; i++)
{
    int k = i > r ? 0 : min(d2[l + r - i + 1], r - i + 1);
    while (0 < i - k - 1 && i + k <= n && str[i - k - 1] == str[i + k]) k++;
    d2[i] = k--;
    if (i + k > r) l = i - k - 1, r = i + k;
    ans = max(ans, d2[i] * 2);
}

 

待续~