Time Limit Exceeds - TASTR

general
, ,
1

Hello,
I am pretty new to code chef, and had tried my first program over here.
I just tried out this question:

hmm… as per the the explanation of the question, its quite unclear, as i have no idea about LCP and Suffix array. I just tried a simple approach and used dynamic arrays to prevent space wastage.

However, i got my time limit exceeded.
here’s my program:
http://www.codechef.com/viewsolution/1968191

basically, i am scanning a string, and then breaking it in sub-strings and passing into a dynamically created 2D array.
I believe its when the sub-strings are compared and looked for duplicate, its taking lots of time.

Could anyone suggest me a better method to ignore duplicate sub-strings?

Thanks

2

Dear you approche the question with Brute force method it’s complexity is O(N^2logN) SO it is getting time limit exceed .you igonre duplicates it has really good explain in the Editorial and the implimentaion of the above method is My AC solution

3

i would suggest that you do not use dynamic allocation as it is normally slower than pre-defined arrays. you should not need to worry about memory in most questions as you can declare arrays up to 1 million(globally) without any problems. Also brute force wont work in most cases so come up with a better algorithm.