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\n", i-len+2);
	}
}

SA后缀数组

　　SA在处理后缀问题上颇有用处，可以进一步来处理最长公共前缀的问题。我的另一篇博客有详细的代码注解。

void build_sa(char *s, int *sa) {
	static int t[maxn], t2[maxn], 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];
	rep0(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;
	}
}

字符串模板集

原文：https://www.cnblogs.com/ac-evil/p/13027439.html