洛谷P4696 [CEOI2011]Matching（KMP）

题目大意

对于整数序列 ((a_1,a_2,cdots,a_n)) 和 (1sim n) 的排列 ((p_1,p_2,cdots,p_n))，称 ((a_1,a_2,cdots,a_n)) 符合 ((p_1,p_2,cdots,p_n))，当且仅当：

({a}) 中任意两个数字互不相同；
将 ((a_1,a_2,cdots,a_n)) 从小到大排序后，将会得到 ((a_{p_1},a_{p_2},cdots,a_{p_n}))。

现在给出 (1sim n) 的排列 ({p}) 和序列 (h_1,h_2,cdots,h_m)，请你求出哪些 ({h}) 的子串符合排列 ({p})。

数据范围

对于 (100\%) 的数据，有 (2le nle mle 1 000 000;1le h_ile 10^9;1le p_ile n)，保证 ({h}) 中的元素互不相同，且 ({p}) 是一个排列。

解题思路

好题！考虑 KMP 和 AC 自动机本质上需要满足什么条件？

如果 (s[1 dots n]=t[1dots n]) 那么 (s[ldots r]=t[l dots r])。

只要快速判断两个字符相等即可，但在这题中如果跳了 nxt 字符串竟是变化的！我们满足另一个条件也可以判断：直接判断两个字符串完全相等即可。

在这题当中，首先将 a 变化为 (a[a_i] = i) 题目条件等价于将 h 的子串 s 排序离散化之后和 a 完全相同。

例如 (s={21,45,23,7,8,4,43}={4,7,5,2,3,1,6}) 考虑匹配跳 nxt 的时候，这个排列是变了的，但是如果最后一个字符在之前的串中的排名相同，那么这个字符就是可以加入末尾的，即使其他数的排名变化了也是依然是相等的。

所以现在我们只需要快速判断一个数的排名，可以先预处理出 p 这个排列中每个数的前驱和后继，注意这里的前驱（后继）是位置在自己前面的第一个小于（大于）自己的数。

那么在 h 这个串上匹配的时候，只用查看对应 p 上的前驱后继是不是真正的前驱后继即可。

这题另一特点就是下标巨多，请仔细考虑！

const int N = 1005000;
int rp[N], aft[N], pre[N], nxt[N], h[N], p[N], m, n;
bool cmp(int t, int *h, int x) {
	if (aft[t] != n + 1 && x > h[rp[aft[t]]]) return 0;
	if (pre[t] && x < h[rp[pre[t]]]) return 0;
	return 1;
}

int ans[N], tp;
int main() {
	read(n), read(m);
	for (int i = 1;i <= n; ++i) read(rp[i]), p[rp[i]] = i, pre[i] = i - 1, aft[i] = i + 1;
	for (int i = n;i >= 1; --i) {
		int nt = aft[p[i]], pr = pre[p[i]];
		aft[pr] = nt, pre[nt] = pr;
	}
	int j = nxt[2] = 1;
	for (int i = 3;i <= n; ++i) {
		while (j && !cmp(p[j + 1], p + i - j - 1, p[i])) j = nxt[j];
		if (cmp(p[j + 1], p + i - j - 1, p[i])) ++j;
		nxt[i] = j;
	}
	j = 0;
	for (int i = 1;i <= m; ++i) {
		read(h[i]);
		while (j && (j == n || !cmp(p[j + 1], h + i - j - 1, h[i]))) j = nxt[j];
		if (cmp(p[j + 1], h + i - j - 1, h[i])) ++j;
		if (j == n) ans[++tp] = i - n + 1; 
	}
	write(tp);
	for (int i = 1;i <= tp; ++i) write(ans[i], ' ');
	return 0;
}

/*

5 10
1 2 5 3 4
1 8 9 6 4 45 32 88 2 7

*/