Complexity of Substring Search in a Set of Strings

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.