完善程序1
给定一个字符串 ,有 组询问,每次给定一个字符串 ,求字符串 是否是 中的一个子 序列。 数据保证 ,所有字符串仅包含小写字母。
#include <iostream> using namespace std; const int BASE = 26; string S, T; int q, Pos[100005][BASE]; int main(){ cin >> S; int n = S.size(); for (int i = 0; i < BASE; i++) ___(1)___ = -1; for (int i = n - 1; i >= 0; i--){ for (int j = 0; j < BASE; j++) ___(2)___; ___(3)___; } cin >> q; while (q--){ cin >> T; int len = T.size(), now = 0; for (int i = 0; ___(4)___; i++) now = ___(5)___; if (now != -1) cout << "YES\n"; else cout << "NO\n"; } return 0; }
(1) 处应填()
Pos[i][n – 1]
Pos[i][n]
Pos[n – 1][i]
Pos[n][i]
(2) 处应填()
Pos[i][j] = Pos[i - 1][j]
Pos[i][j] = Pos[i + 1][j]
Pos[i][j] = Pos[i][j – 1]
Pos[i][j] = Pos[i][j + 1]
(3) 处应填()
Pos[i][S[i] – 'a'] = i
Pos[i][S[i] – 'A'] = i
Pos[i][S[i]] = i
Pos[i][i] = S[i]
.(4) 处应填()
i < len
now != -1
i < len && now != n
i < len && now != -1
(5) 处应填()
Pos[now][T[i] – 'a']
Pos[now][S[i] – 'a']
Pos[now + 1][T[i] – 'a']
Pos[now + 1][S[i] – 'a']
发表评论