Need help in a TRIE problem

Revision en2, by Lakh, 2018-05-24 18:07:35

I am solving the following problem:

Given T (T<=75) testcases . Each testcase consists of N (N<=10^4) strings and Q (Q<=10^4) queries. In each query you are given a number X.The task is to find the most common suffix of length X among the given strings and you need to print how common it is. Sum of length of all strings in a testcase is<=10^5.

Link to problem: http://codeforces.com/gym/101502/problem/G

E.g. Input :

1
5 4

abccba
abddba
xa
abdcba
aneverknow

1
2
4
3

Output:

4
3
1
2

I am inserting the given strings in a trie and storing a variable count in each node to find number of strings along the given path with suffix of length K. Now for all possible length of suffixes I am updating the ans[] array which stores the result for a given prefix of length K. and hence answering queries in O(1) but I am geting TLE. I am not able to optimize it further . How to solve this problem?? My code: https://ideone.com/fNAWjb

Tags string, trie

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Lakh 2018-05-24 18:16:25 6 Tiny change: 'r a given prefix of len' -> 'r a given suffix of len'
en2 English Lakh 2018-05-24 18:07:35 46
en1 English Lakh 2018-05-24 18:04:04 995 Initial revision (published)