|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2018, Number 3, Pages 16–21
(Mi vmumm28)
|
|
|
|
Mathematics
Complexity of search of a substring entering in a set of strings
E. M. Perper Kraftway Corporation PLC, Moscow
Abstract:
The paper considers the problem of listing all occurrences of an arbitrary pattern in the strings from given set. We obtain lower bound for amount of time taken by search algorithms. We also obtain the order of memory volumes required by algorithms with the best order search time.
Key words:
pattern, text, occurrence, string matching, lower bound, higher bound.
Received: 27.09.2017
Citation:
E. M. Perper, “Complexity of search of a substring entering in a set of strings”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2018, no. 3, 16–21; Moscow University Mathematics Bulletin, 73:3 (2018), 98–102
Linking options:
https://www.mathnet.ru/eng/vmumm28 https://www.mathnet.ru/eng/vmumm/y2018/i3/p16
|
|