关于字符串的系统学习&总结。
感觉字符串的相关算法，都是精巧的运用了储存下来的数据信息来挖掘其中的信息。也就是当前问题可以拆成子问题和其他，通过子问题来节省一部分时间复杂度。
感觉这么说好怪）

前缀数组

定义：前缀函数为n个数， $\pi [i]$ 表示字符串s的子串s[0,i]中最长的 前缀和后缀相同的段落
注意，这里说的前缀是真前缀（也就是 $\pi [0]=0$ ）
线性求法：

vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}
Copy

kmp

Z函数

定义：z函数为n个数，z[i]代表以s[i]开头且是s的一个前缀的最长字符串长度。
线性求法：

vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      z[i] = max(0, r - i + 1);
      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    }
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
Copy

AC自动机

后缀数组

后缀自动机

马拉车

求回文串，d1[i]表示以第i位为中心的字符串为回文串的最长长度。（只针对奇数串）
对于偶数串，我们可以在它的每一个字符中间添加特殊符号让其变为奇数串。

//注意，需要将字符串转变为奇数长度串
vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
  int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
  while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
    k++;
  }
  d1[i] = k--;
  if (i + k > r) {
    l = i - k;
    r = i + k;
  }
}
Copy

序列自动机

见我的旧blog