自动搬运

查看原文

来自洛谷，原作者为

	quest_2 你看你在有些方面那么有天赋，如果将来去打工，真是莫大的遗憾了。

搬运于2025-08-24 21:38:47，当前版本为作者最后更新于2020-09-12 22:42:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道 $\mathtt{Trie}$ 树的进阶题。

用到了 $\mathtt{Trie}$ 树上跑 $dfs$ 的做法。

现在看来应该还是简单的。

不过之前没做过这类题的话，思维跨度还是有点大的。

题意稍加简述：

有一病毒串由AGCT四种字母和'?'，'*'两种特殊字符构成。

'?'可以替换成任意一种字母，'*'可以替换成任意一种以字母构成的串（可为空串）。

现在给出 N 个RNA串，求其中有多少RNA串是不能由病毒串转换而来的。

思维稍加讲解:

先走一遍我们想到 $\mathtt{Trie}+dfs$ 为正解的心路历程。

第一眼。字符串匹配问题。

第二眼。单对多字符串匹配问题。必定要打 $\mathtt{Trie}$ 树。

第三眼。不是固定的病毒串，也就是有大量有可能的变化形态。但都跑不出相应的变化范式，就像打二维的走迷宫问题，只有四个可能移动的方向。极有可能用上搜索。

第四眼。关于 $bfs$ 和 $dfs$ 选择哪一个的问题。个人在这里选择了 $dfs$ 。原因是 $dfs$ 在搜索过程中有参数的不断改变，可以更好地表示状态，也更有可读性（个人见解）。

正解我们已经有了，现在我们来想运作流程：

1. 把所有的RNA串都插入 $\mathtt{Trie}$ 中，因为只有RNA串是明确已知的，我们制定策略为：让病毒串去尽力匹配RNA串。

2. 在病毒串上跑 $dfs$ ， 从左往右扫一遍每个字符。扫到的这个字符，决定了我们在 $\mathtt{Trie}$ 树上要怎么向下走（类比字典树的查询）。也就是说， $dfs$ 要传两个参数，一个 $stp$ 代表在病毒串上扫到的位置，一个 $now$ 代表在 $\mathtt{Trie}$ 上走到的位置。

具体上说，他是如何决定走法的？

• 对于一个字母（$\mathtt{AGCT}$）字符，他往哪边走显然是固定的，他必须往这个字母的方向走，（就是普通的 $\mathtt{Trie}$ 树的常规查询操作）。同时，这个病毒串上的字母也已被处理掉，开始扫下一个字符， $stp+1$ ， $\mathtt{Trie}$ 上位置变成当前 $now$ 的一个儿子 。

• 对于一个问号（$\mathtt{?}$）字符，他可以替代任何一个字母字符，也就是 ($\mathtt{AGCT}$）四种情况都有。我们向四个方向都可以走。这个字母同样也被处理掉，开始扫病毒串上的下一个字符， $stp+1$ ， $\mathtt{Trie}$ 上位置变成当前 $now$ 的每个儿子 。

• 对于一个星号（$\mathtt{* }$）字符，情况开始有点复杂。他可以替代任何一个串，这个串可能是空的。那我们可以分类讨论，将其分为 “星号代表空串” 和 “星号不代表空串” 两种情况。

  • 情况一：他代表空串。相当于我们在字典树上不用往下面走一步，什么也不用做，直接扫到病毒串的下一位字符， $stp+1$ ，$\mathtt{Trie}$ 上位置不变。

  • 情况二：他代表并不代表空串。这时一个 $*$ 就可以看做是 一个 $?$ 加上一个 $*$ 。问号以问号的做法做即可，再扫病毒串上的下一个字符， $stp+1$ 。剩下的那个星号也必然不会无限递归下去，因为病毒串迟早是会扫完的，这时若还没有满足答案，就可以直接 return 了。

以上便是搜索部分的大致流程。

但这并没有结束。

代码稍加优化：

搜索的时间复杂度总是让人不放心，究其原因，是我们搜索了太多相同的状态。

还好，我们可以记忆化，这就是 $dfs$ 又一项优势：对于状态的记忆化极为方便。

定义一个名为 $vis$ 的bitset，两个维度，一个维度存 $stp$ ，一个维度存 $now$ 。搜索时，倘若这种状态出现过，这次就不搜了。

实现稍加注释：

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1007;
bitset<1007> vis[500007];
//记忆化需要的bitset，为了省空间

struct Trie//Trie树结构体封装式写法
//我喜欢这个，因为用起来就和STL一样
{
     int ch[500007][5], sz = 0, val[500007];
     //val指以这个位置为结尾的单词数量
     
     void clear()//初始化
     {
          memset(ch, 0, sizeof(ch));
          sz = 0;
     }
     
     int idx(char c)//获取每个字符对应的数码
     //总不能把char当成数组下标吧，map神仙当我没说
     {
          if (c == 'A')
          {
               return 1;
          }
          if (c == 'G')
          {
               return 2;
          }
          if (c == 'T')
          {
               return 3;
          }
          if (c == 'C')
          {
               return 4;
          }
          if (c == '?')
          {
               return 5;
          }
          if (c == '*')
          {
               return 6;
          }
     }
     
     void insert(char s[])//插入基操
     {
          int u = 0, len = strlen(s + 1);
          for (int i = 1; i <= len; i++)
          {
               int x = idx(s[i]);
               if (ch[u][x] == 0)
               {
                    ch[u][x] = ++sz;
               }
               u = ch[u][x];
          }
          val[u]++;
     }
} Tree;

char vir[1007];//病毒串
int N, L;//分别为RNA串的数量，病毒串的长度
int ans = 0;//可以和病毒串匹配的RNA串数量

void dfs(int stp, int now) //模式串的第stp位，在trie树上的位置为now
{
     if (stp == L + 1)//病毒串搜到底了
     {
          ans += Tree.val[now];//更新答案
          Tree.val[now] = 0;//修改val值，避免多加
          return;
     }
     if (vis[now][stp])//记忆化
     {
          return;
     }
     
     int x = Tree.idx(vir[stp]);
     vis[now][stp] = 1;
     
     if (x >= 1 && x <= 4)//若stp位置上是字母
     {
          if (Tree.ch[now][x])
               dfs(stp + 1, Tree.ch[now][x]);
     }
     
     if (x == 5)//若是'?'
     {
          for (int i = 1; i <= 4; i++)
          //向四个方向都可以走
          {
               if (Tree.ch[now][i])
                    dfs(stp + 1, Tree.ch[now][i]);
          }
     }
     
     if (x == 6)//若是*
     {
          dfs(stp + 1, now);//第一种情况：空串
          for (int i = 1; i <= 4; i++)
          //第二种情况：'*'='?'+'*'
          {
               if (Tree.ch[now][i])
               {
                    dfs(stp + 1, Tree.ch[now][i]);
                    //处理'?'
                    dfs(stp, Tree.ch[now][i]);
                    //处理'*'
               }
          }
     }
}
int main()
{
     cin >> vir + 1;
     L = strlen(vir + 1);

     cin >> N;
     Tree.clear();
     
     for (int i = 1; i <= N; i++)
     {
          char RNA[1007];
          cin >> RNA + 1;
          Tree.insert(RNA);
     }
     dfs(1, 0);
     cout << N - ans << endl;//ans是匹配上的RNA串数
     //题目要求的是匹配不上的串数，故为 N-ans
}

最后捞一手蒟蒻的\large\texttt\color{Orchid}\colorbox{white}{博客} ~