以前学习的做的笔记，现在整理一下发出来

• 字符串哈希
• 字典树
• KMP
  • next数组
  • 板子
• 扩展KMP
• Manacher

字符串哈希

常用BKDRHash

unsigned int BKDRHash(char *str)
{
    unsigned int seed = 31, key = 0;
    while (*str)
        key = key * seed + (*str++);
    return key & 0x7fffffff;
}

ull base[maxn];
ull Hash[maxn];

base[0] = 1;
for (int i = 1; i <= len; i++)
    base[i] = base[i - 1] * seed;
Hash[0] = s[0] - 'a' + 1;
for (int i = 1; i < len; i++)
    Hash[i] = Hash[i - 1] * seed + s[i] - 'a' + 1;

字典树

1. map使用:略

2. 压缩空间字典树

int trie[maxn][26];
int num[maxn] = {0};
int pos = 1;

void insert(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int n = str[i] - 'a';
        if (trie[p][n] == 0)
            trie[p][n] = pos++;
        p = trie[p][n];
        num[p]++;
    }
}

int find(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int n = str[i] - 'a';
        if (trie[p][n] == 0)
            return 0;
        p = trie[p][n];
    }
}

KMP

KMP解决的是字符串匹配问题：
一个文本串S，一个模式串P，求P在S中出现的次数

next数组

next[i]为满足P[i-z ~ i-1] = P[0 ~ z-1] 的最大z值
next数组的含义：当前字符以前的字符串中，有多大长度的相同前缀和后缀
P[i-next[i]...i-1] = P[0 ... next[i] - 1]

void kmp_pre(char s[], int m, int next[])
{
    int i = 0, j = next[0] = -1;
    while (i < m) {
        while (j != -1 && x[i] != x[j])
            j = next[j];
        next[++i] = ++j;
    }
}

next数组的深入理解和应用：

1. 沿着next数组一直往前后，得到的是所有前缀，也是当前后缀的字符串。

ABCABCABCAB -> ABCABCAB -> ABCAB -> AB

2. 周期性字符串：n % (n-next[n]) == 0，循环节长度为n-nxet[n]

3. next[]往前跳的步长是一样的，除了最后一次

板子

x[]为模式串, y[]为主串

int kmp_count(char x[], int m, char y[], int n)
{
    int i = 0, j = 0, ans = 0;
    kmp_pre(x, m, next);
    while (i < n) {
        while (j != -1 && y[i] != x[j])
            j = next[j];
        i++; j++;
        if (j >= m) {
            ans++;
            j = next[j];
        }
    }
    return ans;
}

扩展KMP

next[i]: x[i..m-1]与x[0...m-1]的最长公共前缀
extend[i]: y[i..n-1]与y[0///m-1]的最长公共前缀

例:
y = "aaaaabbb"
x = "aaaaac"
next[] = {6, 4, 3, 2, 1, 0}
extend[] = {5, 4, 3, 2, 1, 0, 0, 0}

Manacher

求解问题：给定一个字符串s，找到s中最长的回文子字符串。

引入：
原串：abaaba
修改后的子串：$#a#b#a#a#b#a#
统一奇数长度和偶数长度的回文串，给所有字串一个中心
然后计算回文半径

Ma[i-Mp[i] ~ i+Mp[i]]是回文串
$符号可简化边界判断

算法步骤:

1. 预处理得到字符串Ma
2. 充分利用前面的信息得到数组Mp

时间复杂度和空间复杂度都是O(n)

void Manacher(char s[], int len)
{
    int l = 0;
    Ma[l++] = '$';
    Ma[l++] = '#';
    for (int i = 0; i < l; i++) {
        Ma[l++] = s[i];
        Ma[l++] = '#';
    }
    Ma[l] = 0;
    int mx = 0, id = 0;
    for (int i = 0; i < l; i++) {
        Mp[i] = mx > i ? min(Mp[2*id-i], mx - i) : 1;
        while (Ma[i+Mp[i]] == Ma[i-Mp[i]])
            Mp[i]++;
        if (i = Mp[i] > mx) {
            mx = i + Mp[i];
            id = i;
        }
    }
}