A. Amir, G. Benson, and M. Farach, Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files, Journal of Computer and System Sciences, vol.52, issue.2, pp.299-307, 1996.
DOI : 10.1006/jcss.1996.0023

A. Apostolico, String Editing and Longest Common Subsequences, Handbook of Formal Languages, pp.361-398, 1997.
DOI : 10.1007/978-3-662-07675-0_8
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.6742

A. Apostolico, M. Atallah, and S. E. Hambrusch, New clique and independent set algorithms for circle graphs, Discrete Applied Mathematics, vol.36, issue.1, pp.1-24, 1992.
DOI : 10.1016/0166-218X(92)90200-T
URL : http://doi.org/10.1016/0166-218x(93)90038-p

A. Apostolico, M. Atallah, L. Larmore, and S. Mcfaddin, Efficient Parallel Algorithms for String Editing and Related Problems, SIAM Journal on Computing, vol.19, issue.5, pp.968-998, 1990.
DOI : 10.1137/0219066
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.9057

A. Apostolico, G. M. Landau, and S. Skiena, Matching for Run-Length Encoded Strings, Journal of Complexity, vol.15, issue.1, pp.4-16, 1999.
DOI : 10.1006/jcom.1998.0493
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.2269

O. Arbell, G. M. Landau, and J. Mitchell, Edit distance of run-length encoded strings, Information Processing Letters, vol.83, issue.6, pp.307-314, 2002.
DOI : 10.1016/S0020-0190(02)00215-6

A. Aggarawal and J. Park, Notes on searching in multidimensional monotone arrays, [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pp.497-512, 1988.
DOI : 10.1109/SFCS.1988.21966

T. C. Bell, J. C. Cleary, and I. H. Witten, Text Compression, 1990.

G. Benson, A space efficient algorithm for finding the best nonoverlapping alignment score, Theoretical Computer Science, vol.145, issue.1-2, pp.357-369, 1995.
DOI : 10.1016/0304-3975(95)92848-R

H. Bunke and J. Csirik, An improved algorithm for computing the edit distance of run-length coded strings, Information Processing Letters, vol.54, issue.2, pp.93-96, 1995.
DOI : 10.1016/0020-0190(95)00005-W

K. M. Chao, R. Hardison, and W. Miller, Recent Developments in Linear-Space Alignment Methods: A Survey, Journal of Computational Biology, vol.1, issue.4, pp.271-291, 1994.
DOI : 10.1089/cmb.1994.1.271

M. Crochemore, G. M. Landau, and M. Ziv-ukelson, A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices, SIAM Journal on Computing, vol.32, issue.6, pp.1654-1673, 2003.
DOI : 10.1137/S0097539702402007
URL : https://hal.archives-ouvertes.fr/hal-00619573

M. Crochemore, Transducers and repetitions, Theoretical Computer Science, vol.45, pp.63-86, 1986.
DOI : 10.1016/0304-3975(86)90041-1
URL : https://hal.archives-ouvertes.fr/hal-00619540

M. Crochemore and W. Rytter, Text Algorithms, 1994.
URL : https://hal.archives-ouvertes.fr/hal-00619796

D. Eppstein, Sequence comparison with mixed convex and concave costs, Journal of Algorithms, vol.11, issue.1, pp.85-101, 1990.
DOI : 10.1016/0196-6774(90)90031-9
URL : http://academiccommons.columbia.edu/download/fedora_content/download/ac:142800/CONTENT/cucs-382-88.pdf

P. E. Elias and . Transf, Universal codeword sets and representations of the integers, IEEE Transactions on Information Theory, vol.21, issue.2, pp.194-203, 1975.
DOI : 10.1109/TIT.1975.1055349

D. Eppstein, Z. Galil, and R. Giancarlo, Speeding up dynamic programming, [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pp.488-296, 1988.
DOI : 10.1109/SFCS.1988.21965
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.7067

D. Eppstein, Z. Galil, R. Giancarlo, and G. F. Italiano, Sparse dynamic programming I: linear cost functions, Journal of the ACM, vol.39, issue.3, pp.546-567, 1992.
DOI : 10.1145/146637.146650

M. Farach and M. Thorup, String Matching in Lempel???Ziv Compressed Strings, Algorithmica, vol.20, issue.4, pp.388-404, 1998.
DOI : 10.1007/PL00009202

R. Giancarlo, Dynamic Programming: Special Cases, Pattern Matching Algorithms, pp.201-232, 1997.

H. N. Gabow and R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the fifteenth annual ACM symposium on Theory of computing , STOC '83, pp.209-221, 1985.
DOI : 10.1145/800061.808753

Z. Galil and R. Giancarlo, Speeding up dynamic programming with applications to molecular biology, Theoretical Computer Science, vol.64, issue.1, pp.107-118, 1989.
DOI : 10.1016/0304-3975(89)90101-1

Z. Galil and K. Park, A linear-time algorithm for concave one-dimensional dynamic programming, Information Processing Letters, vol.33, issue.6, pp.309-311, 1990.
DOI : 10.1016/0020-0190(90)90215-J

L. Gasieniec, M. Karpinski, W. Plandowski, and W. Rytter, Randomised efficient algorithms for compressed strings: the finger-print approach, Proc. 7th Annual Symposium On Combinatorial Pattern Matching, pp.39-49, 1996.

L. Gasieniec and W. Rytter, Almost-optimal fully LZW-compressed pattern matching, Proceedings DCC'99 Data Compression Conference (Cat. No. PR00096), 1999.
DOI : 10.1109/DCC.1999.755681
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.6311

D. Gusfield, Algorithms on Strings, Trees, and Sequences, 1997.
DOI : 10.1017/CBO9780511574931

D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, vol.18, issue.6, pp.341-343, 1975.
DOI : 10.1145/360825.360861

D. S. Hirshberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM, vol.24, issue.4, pp.664-675, 1977.
DOI : 10.1145/322033.322044

D. S. Hirshberg and L. L. Larmore, The Least Weight Subsequence Problem, SIAM Journal on Computing, vol.16, issue.4, pp.628-638, 1987.
DOI : 10.1137/0216043

X. Huang and W. Miller, A time-efficient, linear-space local similarity algorithm, Advances in Applied Mathematics, vol.12, issue.3, pp.337-357, 1991.
DOI : 10.1016/0196-8858(91)90017-D
URL : http://doi.org/10.1016/0196-8858(91)90017-d

S. K. Kannan and E. W. Myers, An algorithm for locating non-overlapping regions of maximum alignment score, SIAM J. Comput, vol.25, issue.3, pp.648-662, 1996.
DOI : 10.1007/BFb0029798

J. Karkkainen, G. Navarro, and E. Ukkonen, Approximate String Matching over Ziv???Lempel Compressed Text, Proc. 11th Annual Symposium On Combinatorial Pattern Matching, pp.195-209, 2000.
DOI : 10.1007/3-540-45123-4_18

J. Karkkainen and E. Ukkonen, Lempel-Ziv parsing and sublinear-size index structures for string matching, Proc. Third South American Workshop on String Processing (WSP '96), pp.141-155, 1996.

T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa, Shift-And Approach to Pattern Matching in LZW Compressed Text, Proc. 10th Annual Symposium On Combinatorial Pattern Matching, pp.1-13, 1999.
DOI : 10.1007/3-540-48452-3_1

M. Klawe and D. Kleitman, An Almost Linear Time Algorithm for Generalized Matrix Searching, SIAM Journal on Discrete Mathematics, vol.3, issue.1, pp.81-97, 1990.
DOI : 10.1137/0403009

G. M. Landau, E. W. Myers, and J. P. Schmidt, Incremental String Comparison, SIAM Journal on Computing, vol.27, issue.2, pp.557-582, 1998.
DOI : 10.1137/S0097539794264810
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.1766

G. M. Landau, E. W. Myers, and M. , Ziv-Ukelson, Two Algorithms for LCS Consecutive Suffix Alignment, Proc. 15th Annual Symposium On Combinatorial Pattern Matching, pp.173-193, 2004.

G. M. Landau and M. , On the Common Substring Alignment Problem, Journal of Algorithms, vol.41, issue.2, pp.338-359, 2001.
DOI : 10.1006/jagm.2001.1191

G. M. Landau, B. Schieber, and M. Ziv-ukelson, Sparse LCS Common Substring Alignment, Sparse LCS Common Substring Alignment, pp.259-270, 2003.
DOI : 10.1016/j.ipl.2003.09.006

A. Lempel and J. Ziv, On the Complexity of Finite Sequences, IEEE Transactions on Information Theory, vol.22, issue.1, pp.75-81, 1976.
DOI : 10.1109/TIT.1976.1055501

V. I. Levenshtein, Binary Codes Capable of Correcting Deletions, Insertions and Reversals, Soviet Phys, Dokl, vol.10, pp.707-710, 1966.

J. Ziv and A. Lempel, A universal algorithm for sequential data compression, IEEE Transactions on Information Theory, vol.23, issue.3, pp.337-343, 1977.
DOI : 10.1109/TIT.1977.1055714

J. Ziv and A. Lempel, Compression of individual sequences via variable-rate coding, IEEE Transactions on Information Theory, vol.24, issue.5, pp.530-536, 1978.
DOI : 10.1109/TIT.1978.1055934
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.2892

J. Mitchell, A Geometric Shortest Path Problem, with Application to Computing a Longest Common Subsequence in Run-Length Encoded Strings, Dept. of Applied Mathematics, 1997.

M. G. Main and R. J. Lorentz, An O(n log n) algorithm for finding all repetitions in a string, Journal of Algorithms, vol.5, issue.3, pp.422-432, 1984.
DOI : 10.1016/0196-6774(84)90021-X

G. Navarro, T. Kida, M. Takeda, A. Shinohara, and S. , Arikawa: Faster Approximate String Matching Over Compressed Text, Proc. Data Compression Conference (DCC2001), pp.459-468, 2001.
DOI : 10.1109/dcc.2001.917177
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.2959

V. Mäkinen, G. Navarro, and E. Ukkonen, Approximate Matching of Run-Length Compressed Strings, Proc. 12th Annual Symposium On Combinatorial Pattern Matching, pp.1-13, 1999.

V. Mäkinen, G. Navarro, and E. Ukkonen, Approximate Matching of Run-Length Compressed Strings, Algorithmica, pp.347-369, 2003.

U. Manber, A text compression scheme that allows fast searching directly in the compressed file, Proc. 5th Annual Symposium On Combinatorial Pattern Matching, pp.31-49, 2001.

W. J. Masek and M. S. Paterson, A faster algorithm computing string edit distances, Journal of Computer and System Sciences, vol.20, issue.1, pp.18-31, 1980.
DOI : 10.1016/0022-0000(80)90002-1
URL : http://doi.org/10.1016/0022-0000(80)90002-1

W. Miller and E. W. Myers, Sequence comparison with concave weighting functions, Bulletin of Mathematical Biology, vol.44, issue.2, pp.97-120, 1988.
DOI : 10.1007/BF02459948

G. Navarro and M. Raffinot, A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text, Proc. 10th Annual Symposium On Combinatorial Pattern Matching, pp.14-36, 1999.
DOI : 10.1007/3-540-48452-3_2
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.2377

G. Navarro and M. Raffinot, Boyer???Moore String Matching over Ziv-Lempel Compressed Text, Proc. 11th Annual Symposium On Combinatorial Pattern Matching, pp.166-180, 2000.
DOI : 10.1007/3-540-45123-4_16
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1232

S. B. Needleman and C. D. Wunsch, A general method applicable to the search for similarities in the amino acid sequence of two proteins, Journal of Molecular Biology, vol.48, issue.3, pp.443-453, 1970.
DOI : 10.1016/0022-2836(70)90057-4

D. Sankoff and J. B. , Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison, 1983.

J. P. Schmidt, All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings, SIAM Journal on Computing, vol.27, issue.4, pp.972-992, 1998.
DOI : 10.1137/S0097539795288489

Y. Shabita, T. Kida, S. Fukamachi, M. Takeda, A. Shinohara et al., Speeding Up Pattern Matching by Text Compression, LNCS, vol.1767, pp.306-315, 2000.
DOI : 10.1007/3-540-46521-9_25

T. F. Smith and M. S. Waterman, Identification of common molecular subsequences, Journal of Molecular Biology, vol.147, issue.1, pp.195-197, 1981.
DOI : 10.1016/0022-2836(81)90087-5

E. Ukkonen, Finding approximate patterns in strings, Journal of Algorithms, vol.6, issue.1, pp.132-137, 1985.
DOI : 10.1016/0196-6774(85)90023-9

T. A. Welch, A Technique for High-Performance Data Compression, Computer, vol.17, issue.6, pp.8-19, 1984.
DOI : 10.1109/MC.1984.1659158