洛谷P7469题解

题面

题意：有两个字符串 a 和 b，问 b 中有多少个本质不同子串可以由 a 删除若干个字符得到。
|a|,|b|<=3000

题解：字典树（这个题做法很多，后补）。
把字符串 b 的每个子串打到字典树上。
然后因为 3000^2*26 这个东西比较大，所以不能用 nxt[id][26] 来存储，于是使用链式前向星存图，这样 trie 就建出来了。
接下来考虑如何统计答案。因为要做的是本质不同子串，所以考虑如果 a 是

a.....b.....b

那么我在 a 之后接上第一个 b 肯定比接上第二个 b 优。就是说如果我取 a 的子串是 ab.... 那么这个 b 一定取得是前面那个 b。
这个证明不难。
所以说我对于每个位置去转移，只会考虑这个位置之后的第一个 a/b/c/.../z。
那就好办了。我存储每个位置之后的第一个 a/b/c/../z，然后如果字典树上做到了这个节点，同时能够向下转移的话就直接转移。转移每一位都意味着答案加一。

代码直接放上来以防文字太抽象

struct edge {
	int to, nxt, val;
} e[10000000];
int head[10000000], cnt, triecnt, n;
void add(int u, int v, int w) {
	e[++cnt].to = v;
	e[cnt].nxt = head[u];
	e[cnt].val = w;
	head[u] = cnt;
}
char a[4000], b[4000];
int ind[30], nxta[4000][30];
void insert(int x) {
	int p = 0;
	for(int i = x; i <= n; ++i) {
		int flag = 0;
		for(int j = head[p]; j; j = e[j].nxt) if(e[j].val == b[i] - 'a') {
			flag = 1;
			p = e[j].to;
			break;
		}
		if(!flag) {
			add(p, ++triecnt, b[i] - 'a');
			p = triecnt;
		}
	}
}
int ans;
void find(int u, int a) {
	for(int i = head[u]; i; i = e[i].nxt) if(nxta[a][e[i].val] != -1) {
		++ans;
		find(e[i].to, nxta[a][e[i].val]);
	}
}
int main() {
	ios::sync_with_stdio(0);
	scanf("%d%s%s", &n, a+1, b+1);
	memset(ind, -1, sizeof(ind));
	for(int i = n; i >= 0; --i) {
		for(int j = 0; j < 26; ++j) nxta[i][j] = ind[j];
		if(i) ind[a[i] - 'a'] = i;
	}
	for(int i = 1; i <= n; ++i) insert(i);
	find(0, 0);
	cout << ans;
	return 0;
}