题目地址:https://nanti.jisuanke.com/t/38232
求串A是否为串B的非连续子序列。
AC代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 1e6 + 30; int n, len, rt; char S[maxn], T[maxn]; int par[maxn]; int head[26], last[26]; int ch[maxn][26]; void insert_word(int x)//序列自动机模板 { par[++rt] = last[x]; if (!last[x]) head[x] = rt; for (int i = 0; i < 26; i++) for (int j = last[i]; j && ch[j][x] == 0; j = par[j]) { ch[j][x] = rt; } last[x] = rt; } bool find(char S[]) { int rt, len = strlen(S); for (int i = 0; i < len; ++i) { int x = S[i] - 'a'; if (i == 0) rt = head[x]; else rt = ch[rt][x]; if (rt == 0) return 0; } return 1; } int main() { scanf("%s", &S); len = strlen(S); for (int i = 0; i < len; ++i) { insert_word(S[i] - 'a'); } cin >> n; for (int i = 0; i < n; ++i) { scanf("%s", &T); if (find(T)) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
序列自动机可以O(n)判断一个串是否是另一个串的子串。大致思想是对于一个串的每个互不相同的子串,在其某一位置的字符只需要取最靠前的拿一个,比如aaabab,那么子串ab中的a只需要由原串第一个a产生,b由第一个b产生即可。建立一个类似trie的结构,对原串每一个字符,添加到trie中时只添加在每种字符的最后一个的后面。判断时顺着跑一遍就好了。
void insert_word(int x) { par[++rt] = last[x]; if (!last[x]) head[x] = rt; for (int i = 0; i < 26; i++) for (int j = last[i]; j && ch[j][x] == 0; j = par[j]) { ch[j][x] = rt; } last[x] = rt; }
似乎是个很冷门的东西呢