Need help in a hashing+query problem
Difference between en1 and en2, changed 6 character(s)
I am solving this problem http://codeforces.com/gym/101804/problem/J.↵

Here we are given the alphabet size N (N<=26). So if N=4 ,then the alphabet set is=[A,B,C,D] . Now we are given a permutation of the above alphabet. The permutation represents the encoded value of an alphabet . For e.g. if permutation is [D,C,A,B] then A changes to D, B changes to C , C changes to A and so on. Now Q (Q<=10^5) queries are there of three types:↵

1. 1 s: Add string s to the list. (|s|<5*10^5)↵
2. 2: For all the strings currently in list , encode them according to given permutation.↵
3. 3 s: Check if s is prefix of some string in the current list. (|s|<5*10^5)↵

Sum of length of strings over all queries is<5*10^5.↵

My approach : Here whenever a string is added , I computed all the N encodings of the string as maximum cycle length can be N after which strings will be repeated and stored them in N maps. I stored the hash of prefixes of the string in a map. For type 2 since all strings are encoded so i just took a counter and increment it to (counter+1)%N. For type 3 query i just checked if hash of s is present in map of current counter. however i am getting TLE. Please suggest some optimization to the approach or some other method to solve this. I also implemented this problem with trie but got MLE.

#### History

Revisions Rev. Lang. By When Δ Comment
en2 Lakh 2018-05-21 09:09:41 6
en1 Lakh 2018-05-21 09:05:07 1337 Initial revision (published)