Complexity of Substring Search in a Set of Strings / E. M. Perper. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2018. № 3. P. 16-21 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 98-102].

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.

Key words: pattern, text, occurrence, string matching, lower bound, higher bound.