Lower bounds of temporal and spatial complexity of the substring search problem
E. M. Perper · Discrete Mathematics and Applications · 2014
Abstract We consider the problem of substring search in a set of strings. The problem is the following: given a set of strings and an arbitrary substring, list all strings from the set that contain this substring.We describe search algorithms and obtain lower bounds for the running time and for the memory volume required by the fastest algorithms