后缀数组

代码

void rsort() {

	for (int i = 1; i <= m; ++i) tax[i] = 0;

	for (int i = 1; i <= n; ++i) ++tax[rnk[i]];

	for (int i = 1; i <= m; ++i) tax[i] += tax[i-1];

	for (int i = n; i >= 1; --i) sa[tax[rnk[tmp[i]]]--] = tmp[i];

}

void ssort() {

	for (int i = 1; i <= n; ++i) rnk[i] = a[i], tmp[i] = i;

	m = 127;

	rsort();

	for (int w = 1, p = 0; p < n; w <<= 1) {

		p = 0;

		for (int i = 1; i <= w; ++i) tmp[++p] = n - w + i;

		for (int i = 1; i <= n; ++i) if (sa[i] > w) tmp[++p] = sa[i] - w;

		rsort();

		std::swap(rnk, tmp);

		rnk[sa[1]] = p = 1;

		for (int i = 2; i <= n; ++i) {

			rnk[sa[i]] = (tmp[sa[i]] == tmp[sa[i-1]]

			&& tmp[sa[i]+w] == tmp[sa[i-1]+w]) ? p : ++p;

		}

		m = p;

	}

	for (int i = 1, k = 0; i <= n; ++i) {

		while (a[i+k] == a[sa[rnk[i]-1]+k]) ++k;

		h[rnk[i]] = k;

		if (k) --k;

	}

}

应用

关于后缀数组和后缀自动机，在hihocoder上有一套很好的题（重复旋律）。

最长可重叠重复K次子串问题

(hiho1403)

h数组中长度为k的子串的最小值的最大值。

最长不可重叠重复子串问题

(hiho1407)

二分答案为k，若h数组中有连续的一段大于k的值（即有一个子串重复了），且这一段中最靠前的位置和最靠后的位置之间的差大于k（即这个子串可以不重叠），那么该答案合法。

bool check(int x) {

	int mn = N + 10, mx = 0;

	for (int i = 1, flag = 0; i <= n; ++i) {

		if (h[i] >= x) {

			if (!flag) { // mark

				mx = std::max(mx, sa[i-1]);

				mn = std::min(mn, sa[i-1]);

			}

			mx = std::max(mx, sa[i]);

			mn = std::min(mn, sa[i]);

			flag = 1;

		} else if (flag) {

			flag = 0;

			if (mx - mn >= x) {

				return true;

			}

			mn = N + 10;

			mx = 0;

		}

	}

	return false;

}

注意由于h数组的定义，我们需要标记为mark的部分。

最长公共子串问题

(hiho1415)

将两个子串拼接起来，用'#'分隔，那么两个串的最长公共子串就是保证sa[i]和sa[i-1]不在同一个串内的最大的h[i]。

连续重复次数最多的子串

(hiho1419)

枚举子串长度l和重复起点p，计算重复次数lcp(p, p+l)/l + 1，复杂度\(O(n^2)\)。

考虑优化，我们可以以l的间隔枚举p，考虑某个位置p，记lcp(p, p+l)为R，那么，被我们忽略掉的位置p-1,p-2,p-3...的答案值不会超过R+1。

对于\(p-R\bmod l < x < p\) 的\(x\)，以x为起点的答案值不可能超过R（由公式易得），而对于\(p-l<x<p-R\bmod l\)的\(x\)，以x为起点的答案值也不可能超过以p-R%l的答案值，所以只需计算成倍的p和p-R%l的答案值即可。

for (int l = 1; l <= n; ++l) {

	for (int i = 1; i+l <= n; i += l) {

		int R = lcp(i, i + l);

		ans = std::max(ans, R / l + 1);

		if (i >= l - R%l) {

			ans = std::max(ans,

			lcp(i - l + R%l, i + R%l) / l + 1);

		}

	}

}

不同子串的数目问题

\(\frac{1}{2}n(n+1)-\sum_{i=1}^n h[i]\)

巴特西

[Note]后缀数组