# 【每日一题】7.月月查华华的手机 （枚举 or 序列自动机）

2021-04-14 17:41:51

### 思路一

• $$\mathcal{O}(N)$$
string s, t;
void solve() {
cin >> t;
int m = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == t[m]) m++;
if (m >= t.size()) break;
}
cout << (m >= t.size() ? "Yes" : "No") << "\n";
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int _;
cin >> s;
for (cin >> _; _--;) solve();
return 0;
}


### 思路二

$$tp[i][j]$$ 表示A串第$$i$$个位置后，字符$$j$$首次出现的位置。从后往前扫一遍就出来了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
char s[N];
int tp[N][26];
int main(void) {
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < 26; ++j) tp[i][j] = tp[i + 1][j];
tp[i][s[i + 1] - 'a'] = i + 1;
}
int q;
scanf("%d", &q);
while (q--) {
scanf("%s", s + 1);
int m   = strlen(s + 1);
int pos = 0, flag = 1;
for (int i = 1; i <= m; ++i) {
if (tp[pos][s[i] - 'a']) {
pos = tp[pos][s[i] - 'a'];
} else {
flag = 0;
break;
}
}
cout << (flag ? "Yes" : "No") << "\n";
}
return 0;
}


### 思路三：序列自动机

$$next_{i,j}$$ 代表位置 $$i$$ 后字符 $$j$$ 第一次出现的位置。

void Build(void) {
n = strlen(s + 1);
for (int i = n; i >= 1; i--) {
for (int j = 0; j < 26; j++) fail[i - 1][j] = fail[i][j];
fail[i - 1][s[i] - 'a'] = i;
}
}


bool check(void) {
int m = strlen(t + 1), pos = 0;
for(int i = 1; i <= m; i++) {
pos = fail[pos][t[i] - 'a'];
if(!pos) return false;
}
return true;
}


#include <bits/stdc++.h>
using namespace std;
const int maxs = 1000000 + 7;
int n, T;
char s[maxs], t[maxs];
int fail[maxs][28];
void Build(void) {
n = strlen(s + 1);
for (int i = n; i >= 1; i--) {
for (int j = 0; j < 26; j++) fail[i - 1][j] = fail[i][j];
fail[i - 1][s[i] - 'a'] = i;
}
}
bool check(void) {
int m = strlen(t + 1), pos = 0;
for (int i = 1; i <= m; i++) {
pos = fail[pos][t[i] - 'a'];
if (!pos) return false;
}
return true;
}
int main(void) {
scanf("%s", s + 1);
Build();
scanf("%d", &T);
while (T--) {
scanf("%s", t + 1);
cout << (check() ? "Yes" : "No") << "\n";
}
return 0;
}


https://www.cnblogs.com/RioTian/p/14658846.html