Complément aux
références pricipales (livres).
[ A | B | C |
D | E | F |
G | H | I |
J | K | L |
M | N | O |
P | Q | R |
S | T | U |
V | W | X |
Y | Z ]
R. Baeza-Yates et G. H. Gonnet
A new approach to text searching
Commun. ACM, 35(10):74-82, 1992.
R. Bellman
Dynamic Programming
Princeton University Press, 1957.
J. L. Bentley et R. Sedgewick
Fast algorithms for sorting et searching strings
in
Proceedings of the 8th ACM-SIAM Annual Symposium on Discrete
Algorithms,
New Orleans, Louisiane,
pages 360-369,
1997.
J. Berstel et D. Perrin
Theory of codes
Academic Press, 1985.
A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, M. T. Chen et
J. Seiferas
The smallest automaton recognizing the subwords of a text
Theor. Comput. Sci., 40(1):31-55, 1985.
A. Blumer, A. Ehrenfeucht et D. Haussler
Average size of suffix trees and DAWGS
Discret. Appl. Math., 24:37-45, 1989.
K. S. Booth
Lexicographically least circular substrings
Inf. Process. Lett., 10(4):240-242, 1980.
R. S. Boyer et J. S. Moore
A fast string searching algorithm
Commun. ACM, 20(10):762-772, 1977.
D. Breslauer, L. Colussi et L. Toniolo
On the comparison complexity of the string prefix-matching problem
J. Algorithms, 29(1):18-67, 1998.
D. Breslauer, T. Jiang et Z. Jiang
Rotations of periodic strings et short superstrings
J. Algorithms, 24(2):340-353, 1997.
E. Cambouropoulos, M. Crochemore, C. S. Iliopoulos, L. Mouchard and
Y. J. Pinzon
Algorithms for computing approximate repetitions in musical sequences
in
Proccedings of the 10th Australasian Workshop On Combinatorial
Algorithms,
Perth, Australie,
édités par
R. Raman et J. Simpson,
pages 129-144, 1999.
A. Cardon et M. Crochemore
Partitioning a graph in O(|A|log2|V|)
Theor. Comput. Sci., 19(1):85-98, 1982.
R. Cole
Tight bounds on the complexity of the Boyer-Moore string matching
algorithm
SIAM J. Comput., 23(5):1075-1091, 1994.
M. Crochemore
An optimal algorithm for computing the repetitions in a word
Inf. Process. Lett., 12(5):244-250, 1981.
M. Crochemore
Transducers et repetitions
Theor. Comput. Sci., 45(1):63-86, 1986.
M. Crochemore
Longest common factor of two words
in
Proceedings of the 2nd Theory et Practice of Software
Development,
Pise, Italie,
édité par
H. Ehrig, R. Kowalski, G. Levi et U. Montanari,
Lecture Notes in Computer Science,
volume 249,
pages 26-36,
Springer-Verlag, Berlin, 1987.
M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq,
W. Plandowski et W. Rytter
Speeding up two string matching algorithms
Algorithmica, 12(4/5):247-267, 1994.
M. Crochemore, A. Czumaj, L. Gasieniec, T. Lecroq,
W. Plandowski et W. Rytter
Fast practical multi-pattern matching
Inf. Process. Lett., 71((3-4)):107-113, 1999.
M. Crochemore et T. Lecroq
Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
Inf. Process. Lett., 63(4):195-203, 1997.
M. Crochemore, F. Mignosi et A. Restivo
Automata and forbidden words
Inf. Process. Lett., 67(3):111-117, 1998.
M. Crochemore, F. Mignosi, A. Restivo et S. Salemi
Text compression using antidictionaries
in
Proceedings of the 26th International Colloquium on Automata,
Languages and Programming,
Prague, République Tchèque,
édité par
J. Wiedermann, P. van Emde Boas et M. Nielsen,
Lecture Notes in Computer Science,
volume 1644,
pages 261-270, Springer-Verlag, Berlin, 1999.
M. Crochemore et D. Perrin
Two-way string-matching
J. Assoc. Comput. Mach., 38(3):651-675, 1991.
M. Crochemore et W. Rytter
Squares, cubes et time-space efficient string-searching
Algorithmica, 13(5):405-425, 1995.
M. Crochemore et R. Vérin
On compact directed acyclic word graphs
in
Structures in Logic et Computer Science,
édité par
J. Mycielski, G. Rozenberg et A. Salomaa,
Lecture Notes in Computer Science,
volume 1261,
pages 192-211, Springer-Verlag, Berlin, 1997.
M. O. Dayhoff, W. C. Barker et L. T. Hunt
Establishing homologies in protein sequences
Meth. Enzymol., 91:524-545, 1983.
J.-P. Duval
Factorizing words over an ordered alphabet
J. Algorithms, 4(4):363-381, 1983.
M. Farach
Optimal suffix tree construction with large alphabets
in
Proceedings of the 38th IEEE Annual Symposium on Foundations
of Computer Science,
Miami Beach, Floride,
pages 137-143,
1997.
P. Ferragina et R. Grossi
The string B-tree: A new data structure for string search in external
memory et its applications
J. Assoc. Comput. Mach., 46:236-280, 1999.
M. J. Fischer et M. Paterson
String matching and other products
in
Proceedings SIAM-AMS Complexity of Computation,
édité par
R. M. Karp,
Providence, Rhode Island,
pages 113-125, 1974.
A. S. Fraenkel et J. Simpson
How many squares can a string contain?
J. Combin. Theory Ser. A, 82:112-120, 1998.
Z. Galil
On improving the worst case running time of the Boyer-Moore string
searching algorithm
Commun. ACM, 22(9):505-508, 1979.
Z. Galil et J. Seiferas
Time-space optimal string matching
J. Comput. Syst. Sci., 26(3):280-294, 1983.
R. Giancarlo
Dynamic programming: special cases
in
Pattern matching algorithms,
édité par
A. Apostolico et Z. Galil,
chapitre 7, pages 201-236, Oxford University Press, 1997.
O. Gotoh
An improved algorithm for matching biological sequences
J. Mol. Biol., 162:705-708, 1982.
C. Hancart
Analyse exacte et en moyenne d'algorithmes de recherche d'un motif dans
un texte
Rapport 93-11, IGM, Université de Marne-la-Vallée,
France, 1993.
C. Hancart
On Simon's string searching algorithm
Inf. Process. Lett., 47(2):95-99, 1993.
D. Harel et R. E. Tarjan
Fast algorithms for finding nearest common ancestors
SIAM J. Comput., 13(2):338-355, 1984.
S. Henikoff et J. G. Henikoff
Performance evaluation of amino acid substitution matrices
Proteins, 17:49-61, 1993.
D. S. Hirschberg
A linear space algorithm for computing maximal common subsequences
Commun. ACM, 18(6):341-343, 1975.
J. Holub, C. S. Iliopoulos, B. Melichar and L. Mouchard,
Distributed string matching using finite automata,
in
Proccedings of the 10th Australasian Workshop On Combinatorial
Algorithms,
Perth, Australie,
édités par
R. Raman et J. Simpson,
pages 114-128, 1999.
J. E. Hopcroft
An n log n algorithm for minimizing the states in a
finite-automaton
in
Theory of Machines et Computations,
édité par
Z. Kohavi,
pages 189-196. Academic Press, 1971.
R. N. Horspool
Practical fast searching in strings
Softw. Pract. & Exp. 10(6):501-506, 1980.
A. Hume et D. M. Sunday
Fast string searching
Softw. Pract. & Exp. 21(11):1221-1248, 1991.
J. W. Hunt et T. G. Szymanski
A fast algorithm for computing longest common subsequences
Commun. ACM, 20(5):350-353, 1977.
C. S. Iliopoulos, D. Moore et W. F. Smyth
A characterization of the squares in a Fibonacci string
Theor. Comput. Sci., 172(1-2):281-291, 1997.
J. Karhumäki
On cube-free omega-words generated by binary morphisms
Discret. Appl. Math., 5:279-297, 1983.
R. M. Karp, R. E. Miller et A. L. Rosenberg
Rapid identification of repeated patterns in strings, trees et arrays
in
Proceedings of the 4th ACM Symposium on the Theory of Computing,
Denver, Colorado,
pages 125-136, ACM Press, 1972.
R. M. Karp et M. O. Rabin
Efficient randomized pattern-matching algorithms
IBM J. Res. Dev., 31(2):249-260, 1987.
A. J. Kfoury
A linear-time algorithm to decide whether a binary word contains an
overlap
RAIRO Theoret. Inf. Appl., 22:135-145, 1988.
D. E. Knuth, J. H. Morris, Jr et V. R. Pratt
Fast pattern matching in strings
SIAM J. Comput., 6(1):323-350, 1977.
R. Kolpakov et G. Kucherov
Maximal repetitions in words or how to find all squares in linear time
Rapport LORIA 98-R-227, Laboratoire Lorrain de Recherche en
Informatique et ses Applications, 1998.
R. Kolpakov et G. Kucherov
Finding maximal repetitions in a word in linear time
in
Proceedings of the 40th IEEE Annual Symposium on Foundations
of Computer Science,
New York,
pages 596-604, IEEE Computer Society Press, 1999.
R. Kolpakov et G. Kucherov
On maximal repetitions in words
in
Proceedings of the 12th International Symposium on Fundamentals of
Computation Theory,
Iasi, Roumanie,
édité par
G. Ciobanu et Gh. Paun,
Lecture Notes in Computer Science,
volume 1684,
pages 374-385,
Springer-Verlag, Berlin, 1999.
R. Kolpakov et G. Kucherov
On the sum of exponents of maximal repetitions in a word
Rapport LORIA 99-R-034, Laboratoire Lorrain de Recherche en
Informatique et ses Applications, 1999.
S. R. Kosaraju
Computation of squares in string
in
Proceedings of the 5th Annual Symposium on Combinatorial Pattern
Matching,
Asilomar, Californie,
édité par
M. Crochemore et D. Gusfield,
Lecture Notes in Computer Science,
volume 807,
pages 146-150, Springer-Verlag, Berlin, 1994.
G. M. Landau et U. Vishkin
Efficient string matching with k mismatches
Theor. Comput. Sci., 43(2-3):239-249, 1986.
G. M. Landau et U. Vishkin
Fast string matching with k differences
J. Comput. Syst. Sci., 37(1):63-78, 1988.
V. I. Levenshtein
Binary codes capable of correcting deletions, insertions and reversals
Sov. Phys. Dokl., 6:707-710, 1966.
M. G. Main
Detecting leftmost maximal periodicities
Discret. Appl. Math., 25:145-153, 1989.
M. G. Main et R. J. Lorentz
An O(n log n) algorithm for recognizing repetition
Rapport CS-79-056, Washington State University, Pullman, 1979.
M. G. Main et R. J. Lorentz
Linear time recognition of square free strings
in
Combinatorial Algorithms on Words,
édité par
A. Apostolico et Z. Galil,
NATO Advanced Science Institutes, Series F,
volume 12,
pages 272-278, Springer-Verlag, Berlin, 1985.
U. Manber et G. Myers
Suffix arrays: a new method for on-line string searches
SIAM J. Comput., 22(5):935-948, 1993.
W. J. Masek et M. S. Paterson
A faster algorithm for computing string edit distances
J. Comput. Syst. Sci., 20(1):18-13, 1980.
E. M. McCreight
A space-economical suffix tree construction algorithm
J. Algorithms, 23(2):262-272, 1976.
B. Melichar
Approximate String Matching by Finite Automata
Computer Analysis of Images and Patterns,
édités par
V. Hlavác et R. Sára,
Lecture Notes in Computer Science,
volume 970,
pages 342-349,
Springer-Verlag, Berlin, 1995.
S. P. Mohanty
Shortest string containing all permutations
Discret. Math., 31:91-95, 1980.
Morris, Jr, J. H. et V. R. Pratt,
A linear pattern-matching algorithm
Rapport 40, University of California, Berkeley, 1970.
L. Mouchard
Les algorithmes de comparaison de séquences en biologie
moléculaire
in
Actes de l'école thématique Utilisation et
développements de ressources informatiques en Biologie
moléculaire,
Rouen, France, 1995.
E. W. Myers
An O(ND) difference algorithm et its variations
Algorithmica, 1:251-266, 1986.
E. W. Myers et W. Miller
Optimal alignment in linear space
Comput. Appl. Biosci., 4(1):11-17, 1988.
G. Navarro
A guided tour to approximate string matching
ACM Comp. Surv., à paraitre.
S. B. Needleman et C. D. Wunsch
A general method applicable to the search for similarities in the
amino acid sequence of two proteins
J. Mol. Biol., 48:443-453, 1970.
R. Paige et R. E. Tarjan
Three partition refinement algorithms
SIAM J. Comput., 16(6):973-989, 1987.
W. R. Pearson et D. J. Lipman
Improved tools for biological sequence comparison
Proc. Natl. Acad. Sci. U.S.A., 85:2444-2448, 1988.
D. Perrin
Finite automata
in
Handbook of Theoretical Computer Science, Algorithms and
complexity,
volume A, chapitre 1, pages 1-57,
édité par
J. van Leeuwen,
Elsevier, Amsterdam, Pays-Bas, 1990.
M. Raffinot
Asymptotic estimation of the average number of terminal states in dawgs
in
Proceedings of the 4th South American Workshop on String
Processing,
Valparaiso, Chili,
édité par
R. Baeza-Yates,
pages 140-148, Carleton University Press, 1997.
M. Raffinot
On the multi backward dawg matching algorithm (MultiBDM)
in
Proceedings of the 4th South American Workshop on String
Processing,
Valparaiso, Chili,
édité par
R. Baeza-Yates,
pages 149-165, Carleton University Press, 1997.
A. Restivo et S. Salemi
Some decision results on nonrepetitive words
in
Combinatorial Algorithms on Words,
édité par
A. Apostolico et Z. Galil,
NATO Advanced Science Institutes, Series F,
volume 12,
pages 289-295, Springer-Verlag, Berlin, 1985.
D. Sankoff
The early introduction of dynamic programming into computational
biology
Bioinformatics, 16:41-47, 2000.
A. Sardinas et C. Patterson
A Necessary and Sufficient Condition for the Unique Decomposition of
Coded Messages
IRE Intern. Conv. Record, 8:104-108, 1953.
B. Schieber et U. Vishkin
On finding lowest common ancestors: simplification and parallelization
SIAM J. Comput., 17(6):1253-1262, 1988.
A. Schönhage et V. Strassen
Schnelle multiplikation grosser zahlen
Computing, 7:281-292, 1971.
P. H. Sellers
An algorithm for the distance between two finite sequences
J. Comb. Theory Ser. A, 16:253-258, 1974.
A. O. Slisenko
Detection of periodicities et string matching in real time
J. Sov. Math., 22:1316-1386, 1983.
T. F. Smith et M. S. Waterman
Identification of common molecular sequences
J. Mol. Biol., 147:195-197, 1981.
J. Stoye et D. Gusfield
Simple and flexible detection of contiguous repates using a suffix tree
in
Proceedings of the 9th Annual Symposium on Combinatorial Pattern
Matching,
Piscataway, New Jersey,
édité par
M. Farach-Colton,
Lecture Notes in Computer Science,
volume 1448,
pages 140-152,
Springer-Verlag, Berlin, 1998.
D. M. Sunday
A very fast substring search algorithm
Commun. ACM, 33(8):132-142, 1990.
E. Ukkonen
Algorithms for approximate string matching
Inf. Control, 64(1-3):100-118, 1985.
E. Ukkonen
Finding approximate patterns in strings
J. Algorithms, 6(1-3):132-137, 1985.
E. Ukkonen
On-line construction of suffix trees
Algorithmica, 14(3):249-260, 1995.
R. A. Wagner et M. Fischer
The string-to-string correction problem
J. Assoc. Comput. Mach., 21(1):168-173, 1974.
P. Weiner
Linear pattern matching algorithm
in
Proceedings of the 14th Annual IEEE Symposium on Switching
et Automata Theory,
Washington, DC,
pages 1-11, 1973.
C. K. Wong et A. K. Chandra
Bounds for the string editing problem
J. Assoc. Comput. Mach., 23(1):13-16, 1976.
S. Wu et U. Manber
Fast text searching allowing errors
Commun. ACM, 35(10):83-91, 1992.