Complexity of Substring Search in a Set of Strings
E. M. Perper · Moscow University Mathematics Bulletin · 2018
The paper considers the problem of listing all occurrences of an arbitrary pattern in the strings from given set. We obtain a lower bound for time taken by search algorithms. We also obtain the order of memory amount required by algorithms with the best order search time.