0%

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

题目链接

Description

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

Solution

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

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

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

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

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

时间复杂度$O(|A|+\sum\limits_{i=1}^{n} |B_i|)$

但是很神奇的是,跑的比标程的$O(26\cdot|A|+\sum\limits_{i=1}^{n} |B_i|)$要慢。可能是我假了吧。

Code

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
#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");
}
}

回到开头