如何高效处理字符串查询问题，Samara大学生编程竞赛难题L解析？

本文共计944个文字，预计阅读时间需要4分钟。

给定字符串 s 和一个空字符串 p。需要执行 q 次操作，每次操作是向 p 的末尾添加一个字母或从末尾移除一个字母。

A string s is given. Also there is a string p, and initially it is empty. You need to perform q operations
of kind «add a letter to the end of the string p» and «remove a letter from the end of the string p», and
after performing each operation you must say whether or not s contains p as a subsequence.
Input
The first line contains the string s of length from 1 to 200000, consisting of lowercase Latin letters.
The second line contains a single integer q (1 ≤ q ≤ 200000) — the number of operations.
Each of the next q lines describes an operation in the format «push c», which means «add letter c to the
end of the string p» (c is lowercase Latin letter), or «pop», which means «remove letter from the end of
the string p». The «pop» operations is guaranteed never to be applied to the empty string p.
Output
Output q lines, each of which equals «YES» or «NO», depending on whether or not the string p is contained
in the string s as a subsequence after performing the corresponding operation.
Page 13 of 15
XI Samara Regional Intercollegiate Programming Contest
Russia, Samara, March 11, 2018
Example
standard input standard output
abcabc
30
push a
pop
push a
push a
push a
pop
push c
push b
pop
pop
push b
push c
push c
pop
pop
pop
pop
push b
push c
push c
pop
push b
push c
pop
pop
push a
push b
push c
push a
pop
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES

因为每次询问的是子序列，所以肯定得预处理，做到 O(1) 时间处理；
那么我们要先进行预处理：

for (i = len; i >= 0; i--) { for (j = 0; j < 26; j++)nxt[i][j] = loct[j]; loct[s[i] - 'a'] = i; }

这里的nxt 数组表示字符串的第 i 个位置的字符后面的第 j 的字符所在的位置；
那么我们查询的时候没有合法的位置，自然就是”NO“；

#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<vector> #include<queue> #include<string> #include<bitset> #include<ctime> #include<deque> typedef long long ll; using namespace std; typedef unsigned long long int ull; #define maxn 300003 #define ms(x) memset(x,0,sizeof(x)) #define Inf 0x7fffffff #define inf 0x3f3f3f3f const long long int mod = 1e9 + 7; #define pi acos(-1.0) #define pii pair<int,int> #define eps 1e-7 #define pll pair<ll,ll> ll quickpow(ll a, ll b) { ll ans = 1; a = a % mod; while (b > 0) { if (b % 2)ans = ans * a; b = b / 2; a = a * a; } return ans; } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } int q, len; int nxt[maxn][100], loct[30], res[maxn]; char s[maxn]; char opt[7]; int main() { //ios::sync_with_stdio(false); scanf("%s", s + 1); int len = strlen(s + 1); memset(nxt, -1, sizeof(nxt)); memset(loct, -1, sizeof(loct)); int i, j; for (i = len; i >= 0; i--) { for (j = 0; j < 26; j++)nxt[i][j] = loct[j]; loct[s[i] - 'a'] = i; } cin >> q; int tot = 0, n = 0; res[0] = 0; while (q--) { scanf("%s", opt); if (opt[1] == 'u') { scanf("%s", opt); if (res[tot] != -1 && nxt[res[tot]][opt[0] - 'a'] != -1) { res[tot + 1] = nxt[res[tot]][opt[0] - 'a']; tot++; n++; } else { res[++tot] = -1; } } else { tot--; n = min(n, tot); } if (tot == n)cout << "YES" << endl; else cout << "NO" << endl; } }