What is the fastest way to find all occurrences of a substring?
algorithm, search
Solution
See Suffix array
Applications
The suffix array of a string can be used as an index to quickly locate every occurrence of a substring within the string. Finding every occurrence of the substring is equivalent to finding every suffix that begins with the substring. Thanks to the lexicographical ordering, these suffixes will be grouped together in the suffix array, and can be found efficiently with a binary search. If implemented straightforwardly, this binary search takes O(mlogn) time, where m is the length of the substring. To avoid redoing comparisons, extra data structures giving information about the longest common prefixes (LCPs) of suffixes are constructed, giving O(m + logn) search time.
Problem
This is purely out of curiosity. I was browsing through an article comparing various string search algorithms and noticed they were all designed to find the first matching substring. This got me thinking... What if I wanted to find all occurrences of a substring? I'm sure I could create a loop that used a variant of KMP or BM and dumped each found occurrence into an array but this hardly seems like it would be the fastest. Wouldn't a divide and conquer algorithm be superior? For instance lets say your looking for the sequence "abc" in a string "abbcacabbcabcacbccbabc". - On the first pass find all occurrences of the first character and store their positions. - On each additional pass use the positions from the preceding pass to find all occurrences of next character, reducing the candidates for the next pass with each iteration. Considering the ease with which I came up with this idea I assume someone already came up with it and improved upon it 30 years ago.