can someone provide me a link aur give a hint to generate all substring of a string. i need the fastest way.
If you want to emurate all substrings you cannot do better than O(n^2) because in the worst case you can have O(n^2) unique substrings and its easy to enumerate them just using two loops. But I guess just to print the substring it will take O(n) time. So, overall O(n^3).
But if you want to count the number the number of unique substrings turns out one can do much better using suffix array and lcp combination. This can be achieved in O(n) time and there are easy to code O(n lg^2 n) algos for this method.
1 Like
actually i was solving http://www.codechef.com/problems/AMSTRING probelm…
but i modified it to taking input a integer K and a string S.
now substrings are taken from S itself. lets say s1 and s2.
then what should be the number of pair of string s1,s2 such that DIFF(s1,s2)<=K.
any hint to solve this…
Here is the editorial for the problem.
i have read the tutorial but i am not getting how to approach for a single string…
plz help me…