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 givenpresuffix 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↵
↵
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
My code: https://ideone.com/fNAWjb↵