【每日一题】月月查华华的手机 题解

Description

月月和华华一起去吃饭了。期间华华有事出去了一会儿，没有带手机。月月出于人类最单纯的好奇心，打开了华华的手机。哇，她看到了一片的QQ推荐好友，似乎华华还没有浏览过。月月顿时醋意大发，出于对好朋友的关心，为了避免华华浪费太多时间和其他网友聊天，她要删掉一些推荐好友。但是为了不让华华发现，产生猜疑，破坏了他们的友情，月月决定只删华华有可能搭讪的推荐好友。
月月熟知华华搭讪的规则。华华想与某个小姐姐搭讪，当且仅当小姐姐的昵称是他的昵称的子序列。为了方便，华华和小姐姐的昵称只由小写字母构成。为了更加方便，保证小姐姐的昵称长度不会比华华的长。
现在月月要快速的判断出哪些推荐好友要删掉，因为华华快回来了，时间紧迫，月月有点手忙脚乱，所以你赶紧写个程序帮帮她吧！

Solution

如果这个题是子串而不是子序列的话那就是ac自动机裸题了。

如果是子序列的话就不需要构造自动机了。有一种叫双指针的算法，那么在这里面就可以套用成(n+1)指针法。

一开始所有的小姐姐昵称字符串的指针都放在最头。然后当华华昵称字符串的指针往后移动一格，倘若小姐姐昵称字符串的指针指向的是同一个字符，那么这些指针也跟着往后移动一格。

当小姐姐昵称字符串的指针指向'\0'这个字符时，就可以说这个字符串是华华昵称字符串的子序列了。

所以我们需要快速地找到当前指针指向的某个字符的字符串有哪些，可以对于每一个字符，都存有一个队列表示有哪些指针指向这个字符。这样总的复杂度就不会很高。

时间复杂度

但是很神奇的是，跑的比标程的要慢。可能是我假了吧。

样例解释

由于篇幅关系，只举2个字符串为例：tql、ntt。

红色代表当前这个字符串当前指向的位置，黑色则代表其他位置。

刚开始时
字符串A:
ntt:
tql:

字符串A指针在位置2时
字符串A:
ntt:
tql:

当指针移动到字符串第一个字符t时
字符串A:
ntt:
tql:

此时字符串往后一格：
字符串A:
ntt:
tql:
这两个指针也随之移动

Code

#include<bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  string s; cin >> s;
  int n; cin >> n;
  vector<string> str(n);
  vector<bool> ok(n, false); // 记录某个字符串是否可行
  queue<pair<int, int>> q[26]; // 存当前指向的是字符c的所有指针
  for(int i = 0; i < n; i++) {
    cin >> str[i];
    q[str[i][0] - 'a'].push({i, 0}); // 将指针记录下来
  }
  for(int i = 0; i < int(s.size()); i++) {
    queue<pair<int, int>> tq; // 临时队列 防止连续相同字符导致错误
    while(!q[s[i] - 'a'].empty()) {
      // A代表第A个字符串，B代表是第B个字符
      int A, B; tie(A, B) = q[s[i] - 'a'].front();
      q[s[i] - 'a'].pop();
      if(str[A][B + 1] == '\0') ok[A] = true; // 这个字符串是可行的
      else if(str[A][B + 1] == s[i]) {
        tq.push({A, B + 1}); // 放入临时队列中
      } else {
        q[str[A][B + 1] - 'a'].push({A, B + 1}); // 直接放入队列中
      }
    }
    q[s[i] - 'a'] = tq; // 将临时队列转移
  }
  for(int i = 0; i < n; i++) {
    cout << (ok[i] ? "Yes\n" : "No\n");
  }
}