P7469 [NOI Online 2021 提高组] 积木小赛 题解
empty_zhm
·
·
个人记录
算法：Trie + Dfs
考场心路：
想出这个算法还是经历了一点波折的。
经历的 T1 的折磨之后，脑子非常不好使，当时看大佬用的 子序列自动机（下文自动机都是指此） ，一想也差不多，就写了个二分答案的自动机，想来是后悔（毕竟朴素的完全可以直接过）。洛谷数据 80 pts。
然后过来写代码的时候，发现自动机写其实也怪麻烦的，毕竟判重的 hash 摆在那楞要你用（本人 hash 被卡过无数次）。所以就思考着可不可以用其他的判重，比如 Trie 。写好之后，发现自动机里匹配的步骤和字典树有一点奇妙的联系（自然是朴素自动机）。然后这边思路就出来了。
算法思路
对于自动机思路，我们需要找到可供匹配范围内且顺序最前的相同字符然后转移，转转不已，直到找不到下一个可供匹配的字符（在此题，仅需进行后缀的匹配，将每步转移计入答案即可），然后在 Trie 上，将所得字符串逐个录入树里，然后打上 tag，表示这里是一个完整的串，用以判重。
我们可以发现，在匹配过程中的转移中字符的下标是递增的，而我们字典树的节点的父子关系很明显也暗含着先后关系。
那么我们可以将先后顺序改过来，在 Trie 上将所有可能成为答案的字符串录入，最后再用自动机的思想进行答案合法性的判断。相当于在 Trie 上跑子序列自动机。（？）
## 实现思路
在 `Trie` 上跑自动机不可谓不简单。
我们先思考在自动机里的转移：
1. 枚举 `start` 并使 `at=start` 表示子序列开始匹配的位置。
1. 枚举 `i` 并每次让 `at=nxt[T[i]][at]`，表示 `at` 从 `at` 指向`at`**之后**的**当前匹配字符**的位置。若匹配完 `T` 串则 `T` 为 `S` 的子序列；反正，则 `T` 不为 `S` 子序列。（在此题中，每次转移即代表一个完整的 `T` 串，具体原因可见其他自动机写法的题解）
而在 `Trie` 中，我们也依照此种转移，但因为**从一开头到 `T[i]` 的字符串可表现为其中的根节点到某一节点的路径**而且**其所对应的 `at` 值仅仅会被其父节点的 `at` 值影响**，所以我们**仅需在当前节点找到存储** `at` 的位置，并在子节点继承即可。简略描述如下。
$\texttt{PS:}$ $u$ 即为当前 `Trie` 的节点
1. `u=0` 且 `at=-1` 虚根处无法匹配（第一个字符存于 $0$）
1. 枚举 `Trie[u]` 的子节点使其 `at` 值为当前的 `at+1`
1. 枚举 $i \in [at,n-1]$ 并找到第一个 `i` 使 `S[i]` 与 `Trie[u]` 所表示的字符一致。若找到了，则递归 `2`；反之，则结束该次递归。
这里的优点显而易见，对于 `Trie` 中，其从根到每个叶子节点仅会至多更新 $n$ 次，而易得 `Trie` 上至多仅有 $n$ 个叶子节点。对于这里 $O(n^2)$ 的复杂度，我们完全可以**省略**掉求 $nxt$ 数组的过程。
而且，对于一个 `Trie` 上，**根节点到任意节点的路径能且仅能代表一个本质相同的字符串**，所以可以完美避开判重的问题。
## 复杂度
其中，`Trie` 的大小至多为 $O(\frac{n^2}{2})$，且其中每个节点仅会经过一个，所以时空复杂度均为 $O(n^2)$。并且注意这里的空间常数很大，所以推荐将字典树改为**儿子及兄弟**的存法。
## 代码实现
```cpp
#include<bits/stdc++.h>
#define LL long long
#define N 3010
using namespace std;
struct node
{
int tag;
int son,bro;
node(){tag=son=bro=0;}
}Trie[N*N/2];
//字典树存储（兄弟-儿子存法），tag 即为其表示的字符（儿子-兄弟存法的弊端之一）。
int Tsiz;
inline int Add(int tag)
{
Tsiz++;
Trie[Tsiz].tag=tag;
return Tsiz;
}
//在字典树内新开一个 tag 已知的节点，并返回其指针。
void insert(string a)//字典树的插入
{
int len=a.size();
for(int i=0,u=0;i<len;i++)
{
int v=a[i]-'a';
if(Trie[u].son==0)
Trie[u].son=Add(v);
//若无子节点，则须新建（兄弟-儿子存法弊端之二）
for(int j=Trie[u].son;j;j=Trie[j].bro)//找到代表相同字符的子节点
{
if(Trie[j].tag==v) {u=j;break;}
//若找到，则匹配下一个字符
if(Trie[j].bro==0) Trie[j].bro=Add(v);
//若无，则新建一个
}
}
}
int n,ans;
string S,T;
void dfs(char a,int u,int k)//在字典树上跑自动机的过程。
{
for(int i=k;i<n;i++)
if(S[i]==a||u==0)
{
ans+=(u>0);
//除了虚根节点以外，所有节点皆代表一个本质不同的字符串
for(int j=Trie[u].son;j;j=Trie[j].bro)
dfs(Trie[j].tag+'a',j,i+1);
break;
}
}
int main()
{
cin >> n >> S >> T;
for(int i=0;i<n;i++)
insert(T.substr(i));
//将 T 的所有子串录入（录入所有后缀等效于录入所有子串）
dfs('\0',0,-1);
cout << ans;
return 0;
}
```