[NOI Online 2021 提高组] 积木小赛

题目大意：给定串$A$,$B$，求$B$中有多少本质不同的连续子段是$A$的子序列

$n\leq 3000$

暴力枚举$B$中的子段，同步维护与$A$的匹配指针$p$

每次插入一个字符$c$，找到$A$中$p+1$之后第一个字符$c$，令匹配指针跳过去

可以预处理出这样的下一个字符$nxt_{i,c}$，完成$O(1)$匹配

除此以外，我们还需要对于本质不同去重

如果用$\text{trie}$树去重，需要开一个$\frac{n^2} {2}\cdot 26$的数组，面临着内存不够的问题

你可以信仰不开这么大

也可以去学习一下$\text{DAT(Double Array Trie)}$算法

也可以用$\text{hash+set/map/hash table/sort unique}$

也可以用链表暴力存储trie树的情况，每次暴力for过去找儿子

这样内存均为$O(n^2)$

以下是链表trie树的版本

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=3010,M=N*N/2,INF=1e9+10;
bool Mbe;

int n;
int nxt[N][26];
char A[N],B[N];
struct Edge{ int c,to,nxt; } e[M];
int head[M],cnt;

bool Med;
int main(){
	//fprintf(stderr,"%.2lf\n",(&Med-&Mbe)/1024.0/1024.0);
	freopen("block.in","r",stdin),freopen("block.out","w",stdout);
	n=rd(),scanf("%s%s",A+1,B+1);
	drep(i,n,1) {
		rep(j,0,25) nxt[i][j]=nxt[i+1][j];
		nxt[i][A[i]-'a']=i;
	}
	rep(i,1,n) {
		int u=0,p=0;
		rep(j,i,n) {
			int c=B[j]-'a';
			if(!(p=nxt[p+1][c])) break;
			int v=-1;
			for(int k=head[u];k;k=e[k].nxt) if(e[k].c==c) { v=e[k].to; break; }
			if(~v) u=v;
			else {
				v=++cnt;
				e[v]=(Edge){c,v,head[u]};
				head[u]=v,u=v;
			}
		}
	}
	printf("%d\n",cnt);
}