bzoj 4340 隐身术

Posted on | Views:

SAM + dfs 爆搜.

枚举 B 的子串左端点 $t$ ,即考虑所有是以 $t$ 开头的后缀的前缀.

$k$ 较小,可爆搜之,只要保证每次 $k$ 都在减少, dfs 的层数就是 $O(k)$ 的.

具体地,设状态 $(x,y,z)$ 表示串 $A$ 匹配到了位置 $x$ , 串 $B$ 匹配到了位置 $y$ ,还剩 $z$ 次修改机会.

若 $A_x=B_y$ ,则我们需要先跳过一段连续的可以匹配的段,这样接下来就一定会消耗一次修改机会.

在 SAM 上询问这两个位置的 LCP ,将其跳过即可.

若 $A_x\neq B_y$ ,则必须使用修改操作,可以将 $B_y$ 删掉,或在 $B$ 中加入一个 $A_x$ ,或将 $B_y$ 改成 $A_x$ .

这三种操作分别转移到 $(x,y+1,z-1),(x+1,y,z-1),(x+1,y+1,z-1)$ .

当某一个串匹配完成时,由于可能还剩下了若干修改操作,合法的前缀是一段区间,差分打上标记即可.

时间复杂度 $O(n\log n+n\cdot k^3)$ .

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 2e5 + 10, K = 18, S = 27;
int n, m, k, Log[N * 2];
char A[N], B[N];
namespace SAM
{
	int idx = 1, lst = 1, fa[N], len[N], ch[N][S], pos[N];
	void Extend(int x, int c)
	{
		int p = lst, np = ++idx;
		lst = np, len[np] = len[p] + 1;
		while (p && ch[p][c] == 0)
			ch[p][c] = np, p = fa[p];
		if (!p)
			fa[np] = 1;
		else
		{
			int q = ch[p][c];
			if (len[q] == len[p] + 1)
				fa[np] = q;
			else
			{
				int nq = ++idx;
				len[nq] = len[p] + 1;
				fa[nq] = fa[q], fa[q] = fa[np] = nq;
				memcpy(ch[nq], ch[q], sizeof ch[nq]);
				while (p && ch[p][c] == q)
					ch[p][c] = nq, p = fa[p];
			}
		}
		pos[x] = np;
	}
	vector<int> G[N];
	int tot = 0, ps[N], st[N * 2][K];
	void dfs(int x)
	{
		st[++tot][0] = len[x], ps[x] = tot;
		for (int i = 0; i < G[x].size(); ++i)
		{
			dfs(G[x][i]);
			st[++tot][0] = len[x];
		}
	}
	void init()
	{
		for (int i = 2; i <= idx; ++i)
			G[fa[i]].push_back(i);
		dfs(1);
		for (int j = 1; (1 << j) <= tot; ++j)
			for (int i = 1; i + (1 << j) - 1 <= tot; ++i)
				st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		Log[1] = 0;
		for (int i = 2; i <= tot; ++i)
			Log[i] = Log[i >> 1] + 1;
	}
	int query(int x, int y) // LCP of A[x], B[y]
	{
		if (x > n || y > m)
			return 0;
		x = n + 1 - x, x += m + 1;
		y = m + 1 - y;
		int l = ps[pos[x]], r = ps[pos[y]];
		if (l > r)
			swap(l, r);
		int k = Log[r - l + 1];
		return min(st[l][k], st[r - (1 << k) + 1][k]);
	}
}
using namespace SAM;
int ans = 0, diff[N], t;
void dfs(int x, int y, int z)
{
	int lcp = query(x, y);
	x += lcp, y += lcp;
	if (x > n || y > m)
	{
		int d = z - (n + 1 - x);
		if (d < 0)
			return;
		int l = max(1, y - d - t), r = min(m + 1 - t, y + d - t);
		++diff[l], --diff[r + 1];
		return;
	}
	else if (z)
	{
		dfs(x + 1, y, z - 1);
		dfs(x, y + 1, z - 1);
		dfs(x + 1, y + 1, z - 1);
	}
}
int main()
{
	k = read();
	scanf("%s", A + 1), n = strlen(A + 1);
	scanf("%s", B + 1), m = strlen(B + 1);
	int cur = 0;
	for (int i = m; i >= 1; --i)
		Extend(++cur, B[i] - 'A');
	Extend(++cur, 26);
	for (int i = n; i >= 1; --i)
		Extend(++cur, A[i] - 'A');
	init();
	int L = max(1, n - k), R = min(m, n + k);
	for (t = 1; t <= m; ++t)
	{
		dfs(1, t, k);
		for (int i = L; i <= R; ++i)
			diff[i] += diff[i - 1];
		for (int i = L; i <= R; ++i)
			if (diff[i])
				++ans, diff[i] = 0;
	}
	write(ans, '\n');
	return 0;
}