hi i think this is bytecode 06 problem..
i getting sol for this O(n^3),i heard that we hav sol in method called
suffix array ,i didn't understand how to get O(n^2) using this method
could somebody plz tell me how..
distinct substring
Moderator: Board moderators
-
SilentStrike
- New poster
- Posts: 22
- Joined: Fri Jan 04, 2002 2:00 am
Is the problem just count the number of distinct substrings?
I don't know about suffix arrays, but I do know an O(n^2) solution using tries. You can put each subsring in a trie in O(n^2) time. As you are building the trie, you can count new substrings.
For example, ABABACA
insert A
insert AB [keep pointer to A]
insert ABA [keep pointer to AB]
insert ABAB [keep pointer to ABA]
...
insert ABABACA
insert B
insert BA
..
I don't know about suffix arrays, but I do know an O(n^2) solution using tries. You can put each subsring in a trie in O(n^2) time. As you are building the trie, you can count new substrings.
For example, ABABACA
insert A
insert AB [keep pointer to A]
insert ABA [keep pointer to AB]
insert ABAB [keep pointer to ABA]
...
insert ABABACA
insert B
insert BA
..