OJ Board

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..

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
..