IME Starters Try-outs 2018 J. JHADCBEIGF

J. JHADCBEIGF
time limit per test
1.0 s
memory limit per test
256 MB
input
standard input
output
standard output

The members from Incomprehensive Message Encryptors (IME) are learning a new cipher. This technique, although kinda weird, consists of using a key kk that is a permutation of the alphabet. In other words, if the alphabet ΣΣ is a sequence of nn symbols a1,a2,…,ana1,a2,…,an, the key kk is a sequence of nn symbols ap1,ap2,...,apnap1,ap2,...,apn, for some permutation p1,p2,…,pnp1,p2,…,pn of 1,2,...,n1,2,...,n.

They learned to use the key to encrypt a string SS by the following technique: for each ii in 1,2,…,n1,2,…,n, they switch each occurrence of the character aiai in the string SS by the corresponding character apiapi in the key kk. This substitution occurs for all characters at once, so every substitution doesn’t influence the other ones.

For example, if Σ={A,B,C,D,E}Σ={A,B,C,D,E} and k={E,D,C,A,B}k={E,D,C,A,B}, the encryption will change every symbol AA to EE, BB to DD, CC to CC, DD to AA and EE to BB. So the string ABCBADEABCBADE after encryption turns into EDCDEABEDCDEAB.

After learning the encryption, the members received mm tasks to execute. There are three types of tasks:

  • 11 ss: add the string ss to the dictionary;
  • 22: for each string currently in the dictionary, change it by its encrypted version;
  • 33 ss: check if the string ss is prefix of some string in the dictionary.

Because of how complex it is to encrypt it manually, and they are not really good at programming (by their incomprehensiveness), they need someone to solve these tasks for them. That’s why they gave you this responsibility.

The alphabet is always the first nn uppercase English letters in alphabetical order.

Input

The first line of input contains two integers nn, mm ( 1≤n≤261≤n≤26, 0≤m≤1050≤m≤105) — the size of the alphabet and the number of tasks.

The second line contains one string kk (|k|=n|k|=n) — the initial key. It's guaranteed that kk is a permutation of the alphabet.

The next mm lines contains, each, one integer titi (1≤ti≤31≤ti≤3) — the type of the task ii.

If titi is 11, the line also contains one string sisi (1≤|si|≤5×1051≤|si|≤5×105) — the string to be added to the dictionary.

If titi is 33, the line also contains one string sisi (1≤|si|≤5×1051≤|si|≤5×105) — the string to be checked against the dictionary. It's guaranteed that sisionly contains symbols from the alphabet.

It's guaranteed that there's at least one task of type 33 and that ∑|si|≤5 times105∑|si|≤5 times105.

Output

For each task of type 33, print “YES” if the string is a prefix of some string in the dictionary, and “NO” otherwise.

Examples
input
Copy
5 10
ECABD
1 ABACABA
1 EAAE
2
1 AADE
3 ECEAECE
3 DED
2
3 EAAE
3 BDDB
3 AB
output
Copy
YES
NO
NO
YES
NO
input
Copy
5 12
BCDEA
1 AAAAA
3 AAAAA
2
3 AAAAA
2
3 AAAAA
2
3 AAAAA
2
3 AAAAA
2
3 AAAAA
output
Copy
YES
NO
NO
NO
NO
YES

思路：维护一下整颗字典树的变换次数，插入时加入这个次数变换前的字符串，查询也调用k次变换前的串。于是就是个字典树裸题了。
//指针式，不要乱delete，会把指针指向的那块区域全都删掉
  1 #include <iostream>
  2 #include <fstream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <string>
  8 #include <cstring>
  9 #include <algorithm>
 10 #include <queue>
 11 #include <stack>
 12 #include <vector>
 13 #include <set>
 14 #include <map>
 15 #include <list>
 16 #include <iomanip>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <bitset>
 20 #include <ctime>
 21 
 22 using namespace std;
 23 
 24 #define pau system("pause")
 25 #define ll long long
 26 #define pii pair<int, int>
 27 #define pb push_back
 28 #define mp make_pair
 29 #define clr(a, x) memset(a, x, sizeof(a))
 30 
 31 const double pi = acos(-1.0);
 32 const int INF = 0x3f3f3f3f;
 33 const int MOD = 1e9 + 7;
 34 const double EPS = 1e-9;
 35 
 36 /*
 37 #include <ext/pb_ds/assoc_container.hpp>
 38 #include <ext/pb_ds/tree_policy.hpp>
 39 
 40 using namespace __gnu_pbds;
 41 tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update> T;
 42 */
 43 
 44 int n, m;
 45 char k0[37], k[37], s[500015];
 46 char con[2][27];
 47 void pre() {
 48     for (int i = 1; i <= n; ++i) {
 49         k[k0[i] - 'A' + 1] = 'A' + i - 1;
 50         con[0][i] = 'A' + i - 1;
 51     }
 52 }
 53 struct Trie {
 54     Trie *nex[27];
 55     void ini() {
 56         for (int i = 1; i <= 26; ++i) {
 57             nex[i] = NULL;
 58         }
 59     }
 60 };
 61 void Insert(Trie *T, char s[]) {
 62     int l = strlen(s + 1);
 63     for (int i = 1; i <= l; ++i) {
 64         int x = s[i] - 'A' + 1;
 65         if (NULL == T -> nex[x]) {
 66             T -> nex[x] = new Trie;
 67             T = T -> nex[x];
 68             T -> ini();
 69         } else {
 70             T = T -> nex[x];
 71         }
 72     }
 73 }
 74 bool query(Trie *T, char s[]) {
 75     int l = strlen(s + 1);
 76     for (int i = 1; i <= l; ++i) {
 77         int x = s[i] - 'A' + 1;
 78         if (NULL == T -> nex[x]) {
 79             return false;
 80         } else {
 81             T = T -> nex[x];
 82         }
 83     }
 84     return true;
 85 }
 86 int main() {
 87     scanf("%d%d%s", &n, &m, k0 + 1);
 88     pre();
 89     Trie *T = new Trie;
 90     T -> ini();
 91     int cnt = 0;
 92     while (m--) {
 93         int t;
 94         scanf("%d", &t);
 95         if (1 == t) {
 96             scanf("%s", s + 1);
 97             int l = strlen(s + 1);
 98             for (int i = 1; i <= l; ++i) {
 99                 s[i] = con[cnt][s[i] - 'A' + 1];
100             }
101             Insert(T, s);
102         } else if (2 == t) {
103             cnt ^= 1;
104             for (int i = 1; i <= n; ++i) {
105                 con[cnt][i] = k[con[cnt ^ 1][i] - 'A' + 1];
106             }
107         } else {
108             scanf("%s", s + 1);
109             int l = strlen(s + 1);
110             for (int i = 1; i <= l; ++i) {
111                 s[i] = con[cnt][s[i] - 'A' + 1];
112             }
113             puts(query(T, s) ? "YES" : "NO");
114         }
115     }
116     return 0;
117 }
View Code

　// 数组式

  1 #include <iostream>
  2 #include <fstream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <string>
  8 #include <cstring>
  9 #include <algorithm>
 10 #include <queue>
 11 #include <stack>
 12 #include <vector>
 13 #include <set>
 14 #include <map>
 15 #include <list>
 16 #include <iomanip>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <bitset>
 20 #include <ctime>
 21 
 22 using namespace std;
 23 
 24 #define pau system("pause")
 25 #define ll long long
 26 #define pii pair<int, int>
 27 #define pb push_back
 28 #define mp make_pair
 29 #define clr(a, x) memset(a, x, sizeof(a))
 30 
 31 const double pi = acos(-1.0);
 32 const int INF = 0x3f3f3f3f;
 33 const int MOD = 1e9 + 7;
 34 const double EPS = 1e-9;
 35 
 36 /*
 37 #include <ext/pb_ds/assoc_container.hpp>
 38 #include <ext/pb_ds/tree_policy.hpp>
 39 
 40 using namespace __gnu_pbds;
 41 tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update> T;
 42 */
 43 
 44 int n, m;
 45 char k0[37], k[37], s[2000015];
 46 char con[2][27];
 47 void pre() {
 48     for (int i = 1; i <= n; ++i) {
 49         k[k0[i] - 'A' + 1] = 'A' + i - 1;
 50         con[0][i] = 'A' + i - 1;
 51     }
 52 }
 53 int nex[2000015][27], cnt_node;
 54 void Insert(int sta, char s[]) {
 55     int l = strlen(s + 1);
 56     for (int i = 1; i <= l; ++i) {
 57         int x = s[i] - 'A' + 1;
 58         if (!nex[sta][x]) {
 59             nex[sta][x] = ++cnt_node;
 60             sta = nex[sta][x];
 61         } else {
 62             sta = nex[sta][x];
 63         }
 64     }
 65 }
 66 bool query(int sta, char s[]) {
 67     int l = strlen(s + 1);
 68     for (int i = 1; i <= l; ++i) {
 69         int x = s[i] - 'A' + 1;
 70         if (!nex[sta][x]) {
 71             return false;
 72         } else {
 73             sta = nex[sta][x];
 74         }
 75     }
 76     return true;
 77 }
 78 int main() {
 79     scanf("%d%d%s", &n, &m, k0 + 1);
 80     pre();
 81     int cnt = 0;
 82     while (m--) {
 83         int t;
 84         scanf("%d", &t);
 85         if (1 == t) {
 86             scanf("%s", s + 1);
 87             int l = strlen(s + 1);
 88             for (int i = 1; i <= l; ++i) {
 89                 s[i] = con[cnt][s[i] - 'A' + 1];
 90             }
 91             Insert(0, s);
 92         } else if (2 == t) {
 93             cnt ^= 1;
 94             for (int i = 1; i <= n; ++i) {
 95                 con[cnt][i] = k[con[cnt ^ 1][i] - 'A' + 1];
 96             }
 97         } else {
 98             scanf("%s", s + 1);
 99             int l = strlen(s + 1);
100             for (int i = 1; i <= l; ++i) {
101                 s[i] = con[cnt][s[i] - 'A' + 1];
102             }
103             puts(query(0, s) ? "YES" : "NO");
104         }
105     }
106     return 0;
107 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/BIGTOM/p/9289766.html