题解 P2536 【[AHOI2005]病毒检测】

· · 题解

一道 \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} 上走到的位置。

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

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

但这并没有结束。

代码稍加优化：

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

还好，我们可以记忆化，这就是 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}{博客} ~