Geodesic
Optimal Prefix and Suffix Queries on Texts
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

In this paper, we study a restricted version of the position restricted pattern matching problem introduced and studied by Mäkinen and Navarro [Position-Restricted Substring Searching, LATIN 2006]. In the problem handled in this paper, we are interested in those occurrences of the pattern that lies in a suffix or in a prefix of the given text. We achieve optimal query time for our problem against a data structure which is an extension of the classic suffix tree data structure. The time and space complexity of the data structure is dominated by that of the suffix tree. Notably, the (best) algorithm by Mäkinen and Navarro, if applied to our problem, gives sub-optimal query time and the corresponding data structure also requires more time and space. 
@article{DMTCS_2007_special_253_a23,
     author = {Crochemore, Maxime and Iliopoulos, Costas S. and Rahman, M. Sohel},
     title = {Optimal {Prefix} and {Suffix} {Queries} on {Texts}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3541},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3541/}
}
TY  - JOUR
AU  - Crochemore, Maxime
AU  - Iliopoulos, Costas S.
AU  - Rahman, M. Sohel
TI  - Optimal Prefix and Suffix Queries on Texts
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3541/
DO  - 10.46298/dmtcs.3541
LA  - en
ID  - DMTCS_2007_special_253_a23
ER  - 
%0 Journal Article
%A Crochemore, Maxime
%A Iliopoulos, Costas S.
%A Rahman, M. Sohel
%T Optimal Prefix and Suffix Queries on Texts
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3541/
%R 10.46298/dmtcs.3541
%G en
%F DMTCS_2007_special_253_a23
Crochemore, Maxime; Iliopoulos, Costas S.; Rahman, M. Sohel. Optimal Prefix and Suffix Queries on Texts. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3541. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3541/

Cité par Sources :