I need to iterate through all substrings in order first [1…1], then [1…2], [1…3], …, [1…n], [2…2], [2…3], …, [2…n], …?
http://codeforces.com/blog/entry/6662
What is the advantage of using trie in it?Also how to calculate Longest Common Prefix using trie?In this question we will just iterate through the substrings and count the no of bad ones in it .how we will apply trie?
Refer to this tutorial to learn about trie data-structure.
Hope it helps answer all your doubts.
3 Likes
Depends on what you want to do. If you only want to iterate over the substrings, a trie will have no advantage at all. Also for LCP a regular trie will have no advantage. You should use a Suffix trie for that task.