I am solving this problem http://codeforces.me/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 s: Add string s to the list. (|s|<5*10^5)
- 2: For all the strings currently in list , encode them according to given permutation.
- 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.
