LCS Reference

國璽:

LCS
Year	Author(s)	Time Complexity	Space Complexity	Remark
1974	Wagner and Fischer	O(mn)	O(mn)	ED
1975	Hirschberg	O(mn)	O(n)	D&C, linear space
1977	Hunt and Szymanski	O((n + r) log n)	O(r + n)	avg: O(n log n), worst: O(n² log n), r @ mn
1977	Hirschberg	O(pn + n log n)	O(pn)	(minimal) k-candidate, O(pn + n log s)
1977	Hirschberg	O(p(m+1–p) log n)	O((m–p)² + n)	p @ m
1980	Masek and Paterson	O(n max{1, m/log n})	O(n²/ log n)	4-Rassian algorithm, 1974-unpublish
1982	Nakatsu et al.	O(n(m–p))	O(m²)	-
1984	Hsu and Du	O(pm log(n/p) + pm)	O(pm)	-
1985	Ukkonen	O(Em)	O(E min{m, E})	ED,
1986	Apostolico	O(n + m log n + D log(mn/D))	O(r + m)	Improve Hunt77, r @ mn
1986	Myers	O(E(m + n))	O(m + n)	Longest/shortest path, suffix tree
1987	Kumar and Rangan	O(n(m–p))	O(n)	D&C, contour
1987	Apostolico and Guerra	O(pm + n)	O(D + n)	Remark on Hsu-Du
1990	Chin and Poon	O(n + min{D, pm}) O((n+m)s+min{Ds, pm})	O(D + n) O((n+m)s+D)	DM, D @ r
1992	Apostolico et al.	O(pm)	O(n)	Contour
1992	Eppstein et al.	O(n + Dlog log min{D, mn/D})	O(D + m)	DM, ED
2000	Rick	O(min{pm, p(n–p)})	O(n)	Contour

興彥:

Cyclic string correction
Year	Author(s)	Time Complexity	Space Complexity	Remark
1974	Wagner and Fischer	O(mn)	O(mn)	[Wagn74] linear (edit distance)
1990	Maes	O(n m log n)		[Maes90] Cyclic LCS

Constrained LCS
Year	Author(s)	Time Complexity	Space Complexity	Remark
2003	Tsai	O(pm²n²)		[Tsai03]
2004	Chin	??		[Chin04]

LCS from fragments
Year	Author(s)	Time Complexity	Space Complexity	Remark
2002	Baker and Giancarlo	O((m + n) log \|Σ\| + \|M\| log log min( \|M\|, nm/\|M\| ))		[Bake02] Sparse dynamic programming

String matching with k-mismatches
Year	Author(s)	Time Complexity	Space Complexity	Remark
1986	Galil and Giancarlo	O(nk)		[Gali86] Kangaroo Method: Suffix tree + Lowest common ancestor
1987	Abrahamson	O(n (m log m)^1/2)		[Abra87] find the Hamming Distance at every location
2004	Amir, Lewenstein and Porat	min( O(n (k log k)^1/2), O((n + (nk³)/m) log k) )		[Amir04] \|TEXT\| = n; \|Pattern\| = m; k mismatches

永興:

Edit distance (insert, delete, replace)
Year	Author(s)	Time Complexity	Space Complexity	Remark
1974	Wagner and Fischer	O(mn)	O(mn)	[Wagn74]
1990	Maes	O(n m log n)		[Maes90] Cyclic string

Edit distance with block edits (block moves, block copies, block deletes, block reversals)
Year	Author(s)	Time Complexity	Space Complexity	Remark
2000	S. Muthukrishnan and S. C. Sahinalp	O( log n (log*n)²)-approximation in O(n log n) time		[Muth00]
2002	D. Shapira and J. A. Storer	a simple GREEDY approximation algorithm in O(n) time		[Shap02] 1. prove: NP-complete 2. claim: GREEDY = O(log n)-approximation
2002	G. Cormode and S. Muthukrishnan	O( log n log*n)-approximation in O(n log n) time		[Corm02]
2005	M. Chrobak, P.Kolman and J. Sgall	Shapira's GREEDY		[Chro05] Ω(n^0.4³) = GREEDY = O(n^0.69) 2-MCSP: 3-approximation 4-MCSP: Ω(log n)-approximation
2006	H. Kaplan and N. Shafrir	Shapira's GREEDY		[Kapl06] Ω(n^0.4⁶) = GREEDY

Edit distance for numeric sequence-(reversal, transposition)
Year	Author(s)	Time Complexity	Space Complexity	Remark
1995	J. Kececioglu and D. Sankoff	2-approximation in O(n²) Exact algorithm in O(mL(n,n))		[Kece95] m: size of branch and bound search tree. L(n,n): time to solve a linear program of n variables and n constraints
1996	V. Bafna and P.Pevzner	1.75-approximation		[Bafn96] Reversal
1998	V. Bafna and P.Pevzner	1.5-approximation in O(n²)		[Bafn98] Transposition
1998	D. A. Christie	1.5-approximation in O(n²)		[Chri98] Reversal
2000	M. E. Walter, Z. Dias, and J. Meidanis	2.25-approximation in O(b²)		[Walt00] b: the number of breakpoints
2003	T. Hartman and R. Shamir	1.5-approximation in O(n²)		[Hart03] Transposition

Edit distance for Trees (insert, delete, relabel)
Year	Author(s)	Time Complexity	Space Complexity	Remark
1989	K. Zhang and D. Shasha	O(\|T₁\|²\|T₂\|²)		[Zhan89] \|T\|: number of nodes in T
2003	S. Dulucq and L. Tichit	O(\|T₁\|^1.5\|T₂\|^1.5)		[Dulu03]

Edit distance for arc-annotated sequences

Year

Author(s)

Time Complexity

Space Complexity

Remark

2002

T. Jiang, G. H. Lin, B. Ma, and K. Zhang

Exact algorithm for EDIT(Nested, Plain) in O(n⁴)

Approximation algorithm for EDIT(Crossing, Nested) in O(n³) with ratio max{2w_a/(w_b+w_r), (w_b+w_r)/2w_a}

[Jian02] : W_a: cost for arc altering

W_b: cost for arc breaking

W_r: cost for arc removing

球庭:

LIS
Year	Author(s)	Time Complexity	Space Complexity	Remark
1961	Schensted	O(n log n)		[Sche61]
1977	Hunt and Szymanski	O(n log log n)		[Hunt77]
2000	Bespamyatnikh and Segal	O(n log log n)		[Besp00]
2003	Liben-Nowell, Vee and Zhu	élog(1+1/ε)ù - pass, update time O(log k) or O(log log m)	O(k¹⁺^ε log m)	[Liben03] Streaming data

Windowed LIS
Year	Author(s)	Time Complexity	Space Complexity	Remark
2004	Albert	O(n log log n + OUTPUT)		[Albe04] Sliding Window

LCIS
Year	Author(s)	Time Complexity	Space Complexity	Remark
2004	Yang	O(mn)		[Yang05]
2004	Katriel	O(m log m + np log n)	O(m + np)	[Katr05]
2004	Chan	Two sequence: O(min(r log p, np + r) log log n + n log n)) N sequence: O(min(Nr², Nr log p log^N r)+ Nnlog n)		[Chan05] multiple sequence LCIS, Multidimentional orthogonal range query
2005	Brodal	Two sequence: O((m+np) log log σ + Sort), O(m) when σ = 2, O(n+ n log n) when σ = 3 N sequences: O(min(Nr², rlog^N-1 r log log r) + NSort_Σ(n))	O(m)	[Brod05] multiple sequence LCIS

LIS length distribution
Year	Author(s)	Time Complexity	Space Complexity	Remark
1999	Aldous and Diaconis			[Aldo99] Average 2n^0.5

LIS variation
Year	Author(s)	Time Complexity	Space Complexity	Remark
1990	Kim	O(n log n)		[Kim90] Maximal independent set on permutation graph, stack

LCIS variation
Year	Author(s)	Time Complexity	Space Complexity	Remark
1993	Malucelli, Ottmann and Pretolani	O(r log log n)	O(m)	[Malu93] Noncrossing matching, vEBpq

Weighted LIS variation
Year	Author(s)	Time Complexity	Space Complexity	Remark
1985	W. Hsu	O(n² + r log log n) for circle graph, O(nr) for circular-arc graph	O(r) for circular graph	[Hsu85] Circle graph, circular-arc raph
1992	M. Chang and F. Wang	O(n log log n)		[Chan92] Permutation graph, overlap graph
1993	Yu, Tseng and Chang	Sequential: O(n log log n), Parallel: O(log²n), O(n³/(log n)) processor		[Yu93] Permutation graph, vEBpq, parallel

[Abra87]	K. Abrahamson, Generalized string matching, SIAM J. Computing, Vol. 16, No. 6, pp. 1039-1051, 1987.
[Albe04]	M. H. Albert, A. Golynski, A. M. Hamel, A. Lopez-Ortiz, S. S. Rao, and M. A. Safari, "Longest increasing subsequences in sliding windows," Theoretical Computer Science, Vol. 321, No. 2-3, pp. 405-414, 2004.
[Aldo99]	D. Aldous and P. Diaconis, "Longest increasing subsequences: from patience sorting to the baik-deift-johansson theorem," Bulletin of the American Mathematical Society, Vol. 36, No. 4, pp. 413-432, 1999.
[Amir04]	A. Amir, M. Lewenstein and E. Porat, Faster algorithms for string matching with k mismatches. Journal of Algorithms, Vol. 50, No. 2, pp. 257-275, 2004.
[Apos86]	A. Apostolico, "Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two string," Information Processing Letters, Vol. 23, No. 2, pp. 63-69, 1986.
[Apos87a]	A. Apostolico, "Remark on the Hsu-Du new algorithm for the longest common subsequence problem," Information Processing Letters, Vol. 25, pp. 235-236, 1987.
[Apos87b]	A. Apostolico and C. Guerra, "The longest common subsequence problem revisited," Algorithmica, No. 2, pp. 315-336, 1987.
[Apos92]	A. Apostolico, S. Browne, and C. Guerra, "Fast linear-space computations of longest common subsequences," Theoretical Computer Science, Vol. 92, pp. 3-17, 1992.
[Bafn96]	V. Bafna and P. Pevzner, "Genome rearrangements and sorting by reversals," SIAM Journal of Computing, Vol. 25, No. 2, pp. 272-289, 1996
[Bafn98]	V. Bafna and P. Pevzner, "Sorting by transpositions," SIAM Journal on Discrete Mathematics, Vol. 11, No. 2, pp. 224-240, 1998.
[Bake02]	B. S. Baker and R. Giancarlo, Sparse dynamic programming for longest common subsequence from fragments. Journal of Algorithms, Vol. 42, No. 2, pp. 231-254, 2002.
[Besp00]	S. Bespamyatnikh and M. Segal, "Enumerating longest increasing subsequences and patience sorting," Information Processing Letters, Vol. 76, No. 1-2, pp. 7-11, 2000.
[Brod05]	G. S. Brodal, K. Kaligosi, and I. Katriel, "Faster Algorithms for Computing Longest Common Increasing Subsequences," Tech. Rep. BRICS-RS-05-37, BRICS, Department of Computer Science, University of Aarhus, 2005.
[Chan05]	W.T. Chan, Y. Zhang, S.P.Y Fung, D. Ye, and H. Zhu, "Efficient Algorithms for Finding a Longest Common Increasing Subsequence," The 16th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 3827, pp. 665-674, 2005.
[Chan92]	M. Chang and F. Wang, "Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs," IPL, Vol.43, pp. 293-295, 1992.
[Chin90]	F. Y. L. Chin and C. K. Poon, "A fast algorithm for computing longest common subsequences of small alphabet size," Information Processing Letters, Vol. 13, No. 4, pp. 463-469, 1990.
[Chin04]	F. Y. L. Chin, A. D. Santis, A. L. Ferrara, N. L. Ho, and S. K. Kim, "A simple algorithm for the constrained sequence problems," Information Processing Letters, Vol. 90, No. 4, pp. 175-179, 2004.
[Chri98]	"A 3/2-approximation algorithm for sorting by reversals," in the Proceeding of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 244-252, 1998.
[Chro05]	"The greedy algorithm for the minimum common string partition problem," ACM Transactions on Algorithms, pp. 350-366, 2005.
[Corm02]	G. Cormode and S. Muthukrishnan, "The string edit distance matching problem with moves," In Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Algorithms (SODA), pp. 667-676, 2002.
[Dulu03]	S. Dulucq and L. Tichit, "RNA secondary structure comparison: exact analysis of the zhang-shasha tree edit algorithm," Theoretical Computer Science, pp. 471-484, 2003.
[Epps92]	D. Eppstein, Z. Galil, R. Giancarlo, and G. F. Ltaliano, "Sparse dynamic programming I: Linear cost functions," Journal of the ACM, Vol. 39, pp. 519-545, 1992.	pdf
[Gali86]	Z. Galil and R. Giancarlo, Improved String Matching with k Mismatches, SIGACT NEWS, Vol. 17 , Issue 4, pp. 52-54, 1986.
[Hart03]	T. Hartman and R. Shamir, "A simpler 1.5-approximation algorithm for sorting by transpositions," Combinatorial Pattern Matching 14th Annual Symposium, pp. 156-169, 2003.
[Hirs75]	D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequence," Communications of the Association for Computing Machinery, Vol. 24, pp. 664-675, 1975.	pdf
[Hirs77]	D. S. Hirschberg, "Algorithms for the longest common subsequence problem," Journal of the ACM, Vol. 24, pp. 664-675, 1977.	pdf
[Hsu84]	W. J. Hsu and M. W. Du, "New algorithms for the LCS problem," Journal of Computer and System Sciences, Vol. 19, pp. 133-152, 1984.
[Hsu85]	W. Hsu, "Maximum weight clique algorithms for circular-arc graphs and circle graphs," SIAM J. Computing., Vol. 14, No. 1, pp. 224-231, 1985
[Hunt77]	J. W. Hunt and T. G. Szymanski, "A fast algorithm for computing longest common subsequences," Communications of the ACM, Vol. 20, No. 5, pp. 350-353, 1977.
[Jian02]	T. Jiang, G. H. Lin, B. Ma, and K. Zhang, "A general edit distance between RNA structures," Journal of Computational Biology, pp. 371-388, 2002.
[Katr05]	I. Katriel and M. Kutz, "A Faster Algorithm for Computing a Longest Common Increasing Subsequence," MPI-INF Research Report, 2005
[Kapl06]	H. Kaplan and N. Shafrir, "The greedy algorithm for edit distance with moves," Information Processing Letters, Vol. 97, pp. 23-27, 2006
[Kece95]	J. Kececioglu and D. Sankoff, "Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement," Algorithmica, Vol. 13, No. 1-2, pp. 180-210, 1995.
[Kim90]	H. Kim, "Finding a maximum independent set in a permutation graph," IPL, Vol. 36, pp. 19-23, 1990.
[Kuma87]	S. K. Kumar and C. P. Rangan, "A linear-space algorithm for the LCS problem," Acta Informatica, Vol. 24, pp. 353-362, 1987.
[Libe03]	D. Liben-Nowell, E. Vee and A. Zhu, "Finding longest increasing and common subsequences in streaming data,"
[Mase80]	W. J. Masek and M. S. Peterson, "A faster algorithm computing string edit distance," Journal of Computer and System Sciences, Vol. 20, pp. 18-31, 1980.
[Maes90]	M. Maes, "On a cyclic string-to-string correction problem," Information Processing Letters, Vol. 35, pp. 73-78, 1990.
[Malu93]	F. Malucelli, T. Ottmann and D. Pretoalani, "Efficient labelling algorithms for the maximum noncrossing matching problem," Discrete Mathematics, Vol. 47, pp. 175-179, 1993.
[Muth00]	S. Muthukrishnan and S. C. Sahinalp, "Approximate nearest neighbors and sequence comparison with block operations," In the Proceeding of the 32th Annual ACM Symposium on Theory of Computing (STOC), pp. 416-424, 2000.
[Myer86]	E. W. Myers, "An O(ND) difference algorithm and its variations," Algorithmica, No. 1, pp. 251-266, 1986.	pdf
[Naka82]	N. Nakatsu, Y. Kambayashi, and S. Yajima, "A longest common subsequence algorithm suitable for similar texts," Acta Informatica, Vol. 18, pp. 171-179, 1982.
[Rick00]	C. Rick, "Simple and fast linear space computation of longest common subsequences," Information Processing Letters, Vol. 75, pp. 275-281, 2000.	pdf
[Sche61]	C. Schensted, "Longest increasing and decreasing subsequences," Canadian Journal of Mathematics, Vol. 13, pp. 179-191, 1961.
[Shap02]	D. Shapira, J. A. Storer, "Edit distance with move operations," in: Proc. 13th Annual Symp. on Combinatorial Pattern Matching, Springer-Verlag, Berlin, 2002, pp. 85-98.
[Tsai03]	Y. T. Tsai, "The constrained longest common subsequence problem," Information Processing Letters, Vol. 88, pp. 173-176, 2003.
[Ukko85]	E. Ukkonen, "Algorithms for approximate string matching," Information and Control, Vol. 64, pp. 100-118, 1985.
[Ullm76]	J. D. Ullman, A. V. Aho and D. S. Hirschberg, “Bounds on the Complexity of the Longest Common Subsequence Problem, ”. J. ACM, Vol. 23, No. 1, pp. 1-12, Jan. 1976. DOI= http://doi.acm.org/10.1145/321921.321922	pdf
[Wagn74]	R. A. Wagner and M. J. Fischer, "The string-to-string correction problem," Journal of the ACM, Vol. 21, No. 1, pp. 168-173, 1974.
[Walt00]	M. E. Walter, Z. Dias, and J. Meidanis. "A new approach for approximating the transposition distance," In the Proceedings of SPIRE'2000 - String Processing and Information Retrieval. September, 27-29, 2000. La Coruna, Spain.
[Yang05]	I. H. Yang, C. P. Huang, and K. M. Chao, "A fast algorithm for computing a longest common increasing subsequence," Information Processing Letters, 2005.
[Yu93]	M. Yu, L. Tseng and S. Chang, "Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs," IPL, Vol. 46, pp. 7-11, 1993.
[Zhan89]	K. Zhang and D. Shasha, "Simple fast algorithms for the editing distance between trees and related problems," SIAM Journal on Computing, pp. 1245-1262, 1989.