AcWing 160 匹配统计 – 题解与思路重现

160. 匹配统计 – AcWing题库

又是一道明明很明晰却困了我一个上午的题。完了我刷蓝书的进度要被吊打了

解一 字符串Hash结合二分

$\mathrm{O}(n+m)$预处理出两个字符串的前缀哈希。对于每一个$S$的后缀$suf(i)$，设其与$T$的最大匹配长度为$maxl(i)$。容易发现二者前缀哈希是否相等具有单调性。$\mathrm{O}(\log n)$二分每个后缀的答案，最后统计每种$maxl$的计数即可。代码实现略。

其实昨晚扫一眼题就想到了这个做法。要不是愣是要研究KMP，也不至于沦落到如此地步（

解二 KMP模式匹配与next数组

一开始，我仍然依照解一中的思路，思考如何快速求出对于每一个以$S[i]$开始的后缀，其最长的匹配长度。

考虑KMP匹配的过程。我们总是保存在主串$S$中的位置为$x$时，以$x$结尾的子串能够和$T$的前缀匹配的最长长度$now$。有$S[x-now+1 \dots x]=T[0\dots now-1]$。所以显然，可以用$now$直接更新$maxl(x-now+1)$。但明显漏掉了些什么——因为在子串$S[x-now+1 \dots x]$的子串中，可能也存在一种合法的匹配。所以，我思考是否有可能只根据这个以$S[x]$结尾的最长的匹配来更新子串的信息。

如图所示。图中变量含义均与上文一致。假设现在存在$S[y\dots z]=T[0 \dots z-y],y<z<x$，同时其为后缀$suf(y)$的最长匹配。令$len=z-y+1$。则有$next(z)=len$。

这是很重要的结论。同时我们又知道，在匹配到$S[x-now\dots x]$这个最长匹配之前，一定已经遍历过$z$。则由归纳法可以证明，对于$S$中以$x$结尾的子串，可能存在的匹配长度为$now, next(now-1), next(next(now)-1), \dots$。$next$数组其实构成一棵以$0$为根的树。则对于一个确定的$x$，我们在树上遍历其所有父亲节点，对于一个节点$now’$，存在一个子串$S[x-now’+1 \dots x]$与$T[0 \dots now-1]$相匹配。由此可以更新$S[x-now’+1]$的最长匹配长度。否则，某个位置的匹配将会重复计算——而真正的最长匹配只有一个。

然后我卡住了。因为最坏情况下，这种算法是$\mathrm{O}(NM)$的。因为对于每一个匹配，都需要回溯到$next$的根节点。终于山穷水尽，无奈之下翻看题解。

然后发现一个非常严重的问题：我们其实不需要像解一一样，关心这个子串的开头位置。容易发现，根据$next$数组的定义，在进行上述计算时，如果存在一个最长匹配$S[i\dots i+maxl(i)-1]$，那么有$S[i, i+1],S[i,i+1,i+2], \dots, S[i \dots i+maxl(i)-1]$全部会被计算一次。所以，进行上文所述运算时，对于每一个确定的匹配起点，我们实际上累计了$1$到$maxl$的匹配长度各一次。所以最终求出来的“匹配数”$cnt(i)$，指的是长度至少为$i$的匹配串的出现次数。所以我们根本没有必要每一次都遍历到根节点，结合$next$树的性质——节点$x, y (x<y)$有$y$为$x$的子节点或同级节点，可以从$|T|$倒序扫描到$0$，自底向上地统计$now’$共计出现过多少次。查询询问的是恰好匹配到$len$的长度，那么我们回答$cnt(x)-cnt(x+1)$即可。

除此之外，我还思考过这些问题：

不会出现某一个确定的子串$S[x\dots y]$被重复计算或遗漏的情况吗？

分情况讨论。

如果该子串在KMP匹配过程中，没有作为“当前最长的以$y$结尾的匹配的子串”出现过：那么，只有可能在最长匹配的后缀里找到这个子串。必然有$S[x \dots y]=T[0 \dots y-x]$。根据$next$数组的定义，它必然作为当前$now$的$next$，或者其祖先节点中的一个。且由于KMP匹配过程中，相同的$y$只会被考虑$1$次，所以不会计算重复。

如果$x$是作为在KMP正常匹配的过程中，某个匹配到的最长的子串出现的，再分两种情况：一、该匹配先前没有经过$next$数组跳转。那么显然是从$S[x]=T[0]$一路匹配到$S[y]=T[y-x]$的。这期间已经分别直接计算了$S[x]$到$S[x\dots y]$的所有最大匹配。二、该匹配先前经过了$next$数组跳转。对于跳转之前的计数的正确性的证明，就变成了上图所示的情况；而对于跳转之后，最大匹配的开始处变成$x$的情况，可以转化为上述情况一。

匹配中，可能出现“在第$y+1$位失配了，所以我们根据$next$数组移动标尺”的情况。有可能会导致先前作为“在$y$位置结尾的非最大匹配”（如上图所示）变成下一位的“最大匹配”，然后又被计算一次么？

不会。因为统计完成后，我们已经考虑的终止位置$y$已经向右移动了，不会再在主串$S$中反跳回去，故不用担心这个问题。

论证得这么长，代码却真是简短异常。

提交记录 9347942

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

template <typename T> inline bool read (T &x) {
	x = 0; int f = 1; char c = getchar ();
	for (; c != EOF && !isdigit (c); c = getchar ())
		if (c == '-') f = -1;
	if (c == EOF) return 0;
	for (; c != EOF && isdigit (c); c = getchar ())
		x = (x<<1) + (x<<3) + (c^48);
	x *= f; return 1;
}
#define reint register int
#define inl inline
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair <int, int> pint;

const int N = 2e5 + 10;
int n, m, q, cnt[N];
char s[N], t[N]; int f[N];
int nxt[N], x, now, maxd[N];

inl void build_nxt () {
	x = 1, now = 0;
	while (x < m)
		if (t[now] == t[x]) nxt[x++] = ++now;
		else if (now) now = nxt[now - 1];
		else ++x;
}
inl void KMP () {
	x = now = 0;
	while (x < n) {
		if (s[x] == t[now]) ++x, ++cnt[++now];
		else if (now) now = nxt[now - 1];
		else ++x, ++cnt[0];
		if (now == m) now = nxt[m - 1];
	}
}
inl void update () {
	for (now = m; now; --now)
		cnt[nxt[now - 1]] += cnt[now]; }

int main () {
	/* AW160 匹配统计 吴秋实 */
	read (n), read (m), read (q);
	scanf ("%s%s", s, t);
	build_nxt (); KMP (); update ();
	for (int i = 1; i <= q; ++i)
		read (x), printf ("%d\n", cnt[x] - cnt[x + 1]);

	return 0;
}

由此也可以看出，现在的思维局限性仍然较大，并没有真正做到触类旁通、连点成线地灵活运用。还是要多练题啊。