Editing Longest common subsequence (section)

=== Further optimized algorithms ===
Several algorithms exist that run faster than the presented dynamic programming approach. One of them is [[Hunt–Szymanski algorithm]], which typically runs in <math>O((n + r)\log(n))</math> time (for <math>n > m</math>), where <math>r</math> is the number of matches between the two sequences.<ref>{{Cite book | url=https://books.google.com/books?id=mFd_grFyiT4C&q=hunt+szymanski+algorithm&pg=PA132 |title = Pattern Matching Algorithms|isbn = 9780195354348|last1 = Apostolico|first1 = Alberto|last2 = Galil|first2 = Zvi|date = 1997-05-29| publisher=Oxford University Press }}</ref> For problems with a bounded alphabet size, the [[Method of Four Russians]] can be used to reduce the running time of the dynamic programming algorithm by a logarithmic factor.<ref>{{citation
 | last1 = Masek | first1 = William J.
 | last2 = Paterson | first2 = Michael S. | author2-link = Mike Paterson
 | doi = 10.1016/0022-0000(80)90002-1
 | issue = 1
 | journal = Journal of Computer and System Sciences
 | mr = 566639
 | pages = 18–31
 | title = A faster algorithm computing string edit distances
 | volume = 20
 | year = 1980| doi-access = free
 | hdl = 1721.1/148933
 | hdl-access = free
 }}.</ref>