KMP
KMP别看它短小精悍，用处很大，能应用于很多方面呢。尤其fail (next)数组威力无穷。
void kmp(char *s, int *fail) {
int j = fail[0] = -1;
rep(i, 1, strlen(s)-1) {
while (~j && s[i] != s[j+1]) j = fail[j];
fail[i] = s[i] == s[j+1] ? ++j : -1;
}
}
void match(char *s, char *t, int *fail) {
int j = -1, len = strlen(t);
rep0(i, strlen(s)) {
while (~j && s[i] != t[j+1]) j = fail[j];
s[i] == t[j+1] && j++;
if (j == len-1) printf("%d
", i-len+2);
}
}
扩展KMP（Z算法）
用于处理(s[0:z[i]-1]=s[i,i+z[i]-1])的最大的(z[i])。与KMP类似，核心还是自己匹配自己（毕竟一个是往前，一个是往后，即为两者区别）。
char a[maxn], b[maxn];
int y[maxn], z[maxn];
void zkmp(char *s, int *z) {
int n = strlen(s); z[0] = n;
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i < r) z[i] = std::min(r-i, z[i-l]);
while (i+z[i] < n && s[i+z[i]] == s[z[i]]) z[i]++;
if (i+z[i] > r) l = i, r = i+z[i];
}
}
// 下面用来求解s的所有后缀与t的LCP，结果存到y里面。思路与zkmp类似
void match(char *s, char *t, int *y, int *z) {
int n = strlen(s), m = strlen(t);
for (int i = 0, l = 0, r = 0; i < n; ++i) {
if (i < r) y[i] = std::min(r-i, z[i-l]);
while (i+y[i] < n && y[i] < m && s[i+y[i]] == t[y[i]]) y[i]++;
if (i+y[i] > r) l = i, r = i+y[i];
}
}
AC自动机
KMP的局限性在于只能匹配单模式串，而AC自动机能匹配多模板串。同KMP一样，AC自动机上fail链构成一棵树，指向的父亲都是该结点对应串最长的border。
int ch[20001][26], tag[20001], pt;
void newnode(int x) { memset(ch[x], 0, sizeof ch[x]); tag[x] = 0; }
void ins(char *s, int id) { // id表示模板串编号
int u = 0;
rep0(i, strlen(s)) {
int idx = s[i]-'a';
if (!ch[u][idx]) newnode(ch[u][idx] = ++pt);
u = ch[u][idx];
}
tag[u] = id;
}
int fail[20001];
void build_ac() {
static int q[20001], l, r;
l = r = 0; memset(fail, 0, sizeof fail);
rep0(i, 26)
if (ch[0][i]) fail[q[r++] = ch[0][i]] = 0;
while (l < r) {
int u = q[l++];
rep0(i, 26)
ch[u][i] ? fail[q[r++] = ch[u][i]] = ch[fail[u]][i] : ch[u][i] = ch[fail[u]][i];
// 这里面将Trie空的子结点顺道匹配了，这个是**很重要**的trick
}
}
void find(char *s) {
int u = 0;
rep0(i, strlen(s)) {
int idx = s[i]-'a';
u = ch[u][idx];
for (int v = u; v; v = fail[v]) if (tag[v]) ans[tag[v]]++;
// 这个是不优秀的写法，实际上应该在fail树上打标记，最后dfs求解
}
}
序列自动机
用来处理字符串子序列匹配的问题。相关衍生问题可能会结合数据结构和DP。
int n, q, m;
std::vector<int> pos[maxm]; // 由于|Σ|过大，采用vector二分转移
int main() {
scanf("%d%d%d%d", &n, &n, &q, &m);
rep0(i, n) {
int x; scanf("%d", &x);
pos[x].push_back(i+1);
}
while (q--) {
int len, now = 0; scanf("%d", &len);
while (len--) {
int x; scanf("%d", &x);
if (~now) {
std::vector<int>::iterator it = std::upper_bound(pos[x].begin(), pos[x].end(), now);
if (it != pos[x].end()) now = *it; else now = -1;
}
}
printf("%s
", ~now ? "Yes" : "No");
}
return 0;
}
后缀自动机（SAM）
SAM是一个非常强力的工具，能应用于很多很多方面。
struct Node {
int ch[26], len, fa; // 主要的信息
int val; // 辅助信息：可能用于dp等方面
} st[maxn << 1];
int last, pt;
void newnode(int x) { memset(st[x].ch, 0, sizeof st[x].ch); st[x].fa = -1; st[x].val = 0; }
// 初始化结点
void init() { newnode(last = pt = 0); }
// 初始化整个SAM
void extend(int x) { // 拓展一个字符
int p = last, cur = ++pt;
newnode(cur); st[cur].val = 1, st[cur].len = st[last].len+1;
for (; ~p && !st[p].ch[x]; p = st[p].fa) st[p].ch[x] = cur; // 没边往上一直跳连边
if (p == -1) st[cur].fa = 0; // case 1 跳到了根结点上面：fa直接设成根0
else {
int q = st[p].ch[x];
if (st[p].len + 1 == st[q].len) st[cur].fa = q;
// case 2 发现子状态q只有一种字串，不用拆分结点
else { // case 3 要拆分结点，维护信息
int cpy = ++pt;
memcpy(&st[cpy], &st[q], sizeof(Node));
st[cpy].val = 0; st[cpy].len = st[p].len+1; st[q].fa = st[cur].fa = cpy;
for (; ~p && st[p].ch[x] == q; p = st[p].fa) st[p].ch[x] = cpy;
}
}
last = cur; // 修改last，这个是全串所对应的状态
}
Manacher
用离线在(O(n))处理(hw)数组。(hw_i)表示以(i)为回文中心可拓展的最长的回文串的半径（长度+1/2）。这里只能找到长度为奇数的回文串。为了方便，在所有字符之间以及开头结尾插入分隔符(#)，这样就可以处理长度为偶数的回文串了。
// 注意此时字符串s已经被处理过了，其中s='!'+加入分隔符的原串。加上'!'是为了防止回文拓展时溢出。
void manacher() {
for (int i = 1, mid = 0, r = 0; i < n; i++) {
hw[i] = i < r ? std::min(hw[mid*2-i], r-i) : 1; // 利用以前的信息
while (s[i+hw[i]] == s[i-hw[i]]) hw[i]++; // 拓展
if (i+hw[i] > r) mid = i, r = i+hw[i]; // 维护最右的信息
}
}
SA后缀数组
SA在处理后缀问题上颇有用处，可以进一步来处理最长公共前缀的问题。我的另一篇博客有详细的代码注解。
void build_sa(char *s, int *sa) {
static int t[maxn << 1], t2[maxn << 1], c[maxn], *x = t, *y = t2, n, m;
n = strlen(s), m = 'z'+1;
rep0(i, m) c[i] = 0;
rep0(i, n) c[x[i] = s[i]]++;
rep(i, 1, m) c[i] += c[i-1];
per0(i, n) sa[--c[x[i]]] = i;
for (int k = 1; k < n; k <<= 1) {
int p = 0;
rep(i, n-k, n-1) y[p++] = i;
rep0(i, n) if (sa[i] >= k) y[p++] = sa[i]-k;
rep0(i, m) c[i] = 0;
rep0(i, n) c[x[y[i]]]++;
rep(i, 1, m) c[i] += c[i-1];
per0(i, n) sa[--c[x[y[i]]]] = y[i];
std::swap(x, y);
p = 1; x[sa[0]] = 0;
rep(i, 1, n-1)
x[sa[i]] = y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] ? p-1 : p++;
if ((m = p) == n) return;
}
}
Height数组和LCP
// 运用引理ht[rk[i]]>=ht[rk[i-1]]-1
void get_ht(char *s, int *sa, int *ht) {
static int rk[maxn], j; j = 0;
rep0(i, strlen(s)) rk[sa[i]] = i;
rep0(i, strlen(s)) {
j && j--;
if (rk[i]) while (s[i+j] == s[sa[rk[i]-1]+j]) j++;
ht[rk[i]] = j;
}
}
...
RMQ::query(rk[i], rk[j]); // rk[i]<rk[j]，查询后缀i和j的LCP
结语
有很多模板博主还是不会的（嘤～）。不过上述模板可以应对很多的字符串问题，无非就是结合些数据结构或者DP。上面的字符串算法更多的是运用了等价和信息利用的思想，这些是很重要的。