Geodesic
Complexity of search of a substring entering in a set of strings
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2018), pp. 16-21 
E. M. Perper. Complexity of search of a substring entering in a set of strings. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2018), pp. 16-21. http://geodesic.mathdoc.fr/item/VMUMM_2018_3_a2/
@article{VMUMM_2018_3_a2,
     author = {E. M. Perper},
     title = {Complexity of search of a substring entering in a set of strings},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {16--21},
     year = {2018},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2018_3_a2/}
}
TY  - JOUR
AU  - E. M. Perper
TI  - Complexity of search of a substring entering in a set of strings
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2018
SP  - 16
EP  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2018_3_a2/
LA  - ru
ID  - VMUMM_2018_3_a2
ER  - 
%0 Journal Article
%A E. M. Perper
%T Complexity of search of a substring entering in a set of strings
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2018
%P 16-21
%N 3
%U http://geodesic.mathdoc.fr/item/VMUMM_2018_3_a2/
%G ru
%F VMUMM_2018_3_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Knuth D.E., Morris J.H., Pratt V.B., “Fast pattern matching in strings”, SIAM J. Comput., 6:2 (1977), 323–350 | DOI | MR | Zbl

[2] Galil Z., “On improving the worst case running time of the Boyer–Moore string searching algorithm”, Communs ACM, 22:9 (1979), 505–508 | DOI | MR | Zbl

[3] Navarro G., Mäkinen V., “Compressed fulltext indexes”, ACM Comput. Surv., 39:1 (2007), 2 | DOI

[4] Gasfild D., Stroki, derevya i posledovatelnosti v algoritmakh. Informatika i vychislitelnaya biologiya, Nevskii Dialekt; BKhV-Peterburg, SPb., 2003

[5] Gasanov E.E., Kudryavtsev V.B., Teoriya khraneniya i poiska informatsii, Fizmatlit, M., 2002

[6] Kudryavtsev V.B., Gasanov E.E., Podkolzin A.S., Osnovy teorii intellektualnykh sistem, Maks Press, M., 2016

[7] Perper E.M., “Poryadok slozhnosti zadachi poiska v mnozhestve slov vkhozhdenii podslova”, Intellektualnye sistemy. Teoriya i prilozheniya, 19:1 (2015), 99–116 | MR