Ravi wrote:
i need to know a substring which is in lexicographically i^th^ position. that is why, i am firstly adding all unique substring into arraylist, then performing lexicographical sorting but if i could get that substring without processsing two for loops then it will definitely saves my time and improves the program too.
I'm not a math guy, so I may be way off here, but if nothing else, maybe this will get you thinking about some possible approaches:
The lexicographically first substring will consist of exactly one character--the lexicographically first character in the string.
The next one will be that character followed by one more character--the next character after that one, if there are any, otherwise it will be a single character--the lexi'ly second one in the string.
and so on...
So, start by building a list of indices in lexi' order of the chars. For instance if you have the string "blue", your list would be [0, 3, 1, 2], since the 0th character ('b') is the lexi'ly first, and so on.
You keep building 1-char-longer substrings from the lexi'ly first char, until you either reach the i'th one or have hit the end of the string. Then move on to the next char, and so on
b
bl
blu
blue
(next char is at index 3)
e
(no more chars, next is at 1)
l
lu
I don't know if that's any less than O(n^2), and I can't be bothered to figure it out.
As a further refinement, rather than actually generating each substring, you can compute them. Given [0, 3, 1, 2], we know there are str.len substrings starting at position 0, str.len - 3 starting at position 1 (so str.len + str.len - 3 so far), and so on. So if we're looking for i=6, then 4-0=1 < 6, so add 4-3=1 for a total of 5<6 so add 4-1=3 for a total of 8>6, so we know now exactly where to find lexi'ly 6th substring
This assumes each char appears only once. If a char appears more than once, the logic gets somewhat more complicated, but not terribly so, I don't think.
Personally, you probably should go investigate suffix trees a bit more. I don't know what they are or how/if they fit here, but it might be worth looking into.
Edited by: jverd on Mar 30, 2012 6:45 PM