事先說(shuō)明，這個(gè)算法你大概率在競(jìng)賽環(huán)境用不到。因?yàn)楦?jìng)賽環(huán)境的數(shù)據(jù)都是構(gòu)造出來(lái)的最壞數(shù)據(jù)。這個(gè)算法在這種數(shù)據(jù)下的表現(xiàn)可以被卡到O(nmlog(n))，空間O(nm)。并且構(gòu)造這種數(shù)據(jù)很容易，令str1="AAAAA"，str2="AAAAAAA"即可。

但是相對(duì)的，它在兩個(gè)序列的元素值域比較大，匹配數(shù)比較少的情況下會(huì)非常有效。

本文假設(shè)你已經(jīng)學(xué)過(guò)了最長(zhǎng)公共子序列以及其經(jīng)典的n*m的dp做法，后文提到的所有LCS是Longest Common Subsequence的縮寫(xiě)。

背景（廢話(huà)）

小組里給了個(gè)語(yǔ)料對(duì)齊的任務(wù)，用實(shí)際的例子來(lái)說(shuō)，可以看這個(gè)鏈接：https://wiki.mnbvc.org/doku.php/%E5%AF%B9%E9%BD%90%E7%AE%97%E6%B3%95#%E5%9F%BA%E4%BA%8E%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97

方案用了一個(gè)最長(zhǎng)公共子序列，調(diào)的是pylcs這個(gè)庫(kù)，里面的C++實(shí)現(xiàn)用了兩個(gè)n * m的int數(shù)組，于是我們的程序在跑長(zhǎng)達(dá)1MB的大文件時(shí)不出意外的炸內(nèi)存了= =

炸內(nèi)存還不是主要的問(wèn)題，稍微魔改了一下，優(yōu)化到只用1/32的內(nèi)存，雖然現(xiàn)在是能跑了，但是這個(gè)文件仍然需要跑15分鐘。其實(shí)用LCS來(lái)做這個(gè)問(wèn)題不是很有效，我本來(lái)都想把方案改進(jìn)一下，但是網(wǎng)上沖浪的時(shí)候遇到了這么一個(gè)期望nlogn的算法，看了一下覺(jué)得還挺高效的，行，哥們不做方案優(yōu)化了，重拾舊業(yè)開(kāi)始搞算法。

參考資料

https://en.wikipedia.org/wiki/Hunt%E2%80%93Szymanski_algorithm#cite_ref-8 維基的資料

https://codeforces.com/blog/entry/91581 算法基本思想講解

https://cse.hkust.edu.hk/mjg_lib/bibs/DPSu/DPSu.Files/HuSz77.pdf 論文

https://github.com/sgtlaugh/algovault/blob/0ba0b3eb0d2e31e78de05da188f13d8d7d0365ae/code_library/hunt_szymanski.cpp 一個(gè)短小精悍的C++實(shí)現(xiàn)，但是只能求長(zhǎng)度，直接用它的下標(biāo)數(shù)組生成LCS是不對(duì)的

https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1460&context=cstech 這個(gè)是下界改進(jìn)，和本文無(wú)關(guān)，我還沒(méi)看

思想

如果我們需要求LCS的兩個(gè)序列比較隨機(jī)，或者說(shuō)它們的匹配比較稀疏，這樣我們?cè)谒鉒CS的時(shí)候，可以從匹配出發(fā)，而不需要算一個(gè)n*m的dp。舉個(gè)例子，我們有acbdd和cabad兩個(gè)序列，把它們畫(huà)成一個(gè)匹配矩陣就是這樣：

如圖，藍(lán)色格子表示匹配上的元素。我們可以只關(guān)心圖中的藍(lán)色格子。

算藍(lán)格子很簡(jiǎn)單，隨便用一個(gè)桶數(shù)組或者哈希表就能實(shí)現(xiàn)。

現(xiàn)在，我們的LCS問(wèn)題可以在圖中轉(zhuǎn)化成一個(gè)非常形象的問(wèn)題：尋找一個(gè)藍(lán)格子表，使得其橫坐標(biāo)在圖中嚴(yán)格遞增，同時(shí)縱坐標(biāo)嚴(yán)格遞減。

（是不是有點(diǎn)像二維偏序的味道？）

于是幾何佬半途搶過(guò)鍵盤(pán)開(kāi)始動(dòng)手了：我先掃描線(xiàn)從左到右搞一下橫坐標(biāo)，然后我用一個(gè)std::set這樣的有序容器維護(hù)一下縱坐標(biāo)就做完了。

我知道你很急，但是我們先別急。首先，我們會(huì)做最長(zhǎng)上升子序列，O(nlogn)做完，一個(gè)數(shù)組二分插入貪心完事。然后，如果我們把這個(gè)圖稍微變一下……

由于我們按列展開(kāi)了這個(gè)表，每列最多只有一個(gè)元素，然后現(xiàn)在我讓你從左到右橫著掃一遍，讓你求一個(gè)最長(zhǎng)嚴(yán)格下降子序列，是不是會(huì)做了？

為什么是倒序枚舉？因?yàn)槲覀儾幌Ｍ粋€(gè)匹配被計(jì)入答案多次，因?yàn)檎蛎杜e會(huì)計(jì)入。感性理解一下。

然后就剩最后一個(gè)問(wèn)題了，我們把它倒序枚舉之后，就不能恢復(fù)原來(lái)的匹配串了。

如圖，我們從左到右掃描srcyeelxduw的時(shí)候，我們希望得到的LCS應(yīng)該是rydu，但是由于我們拿一個(gè)數(shù)組記LIS，在更新的時(shí)候這個(gè)數(shù)組是這么變的：

{0: r}

{0: r, 1: y}

{0: x, 1: y}

{0: x, 1: y, 2: d}

{0: x, 1:?d, 2: d}

{0: x, 1:?d,?2: d, 3: u}

雖然最后LCS的長(zhǎng)度是算對(duì)了，但是因?yàn)槲覀兡壳皼](méi)記它上一次連接的是哪個(gè)字符，所以我們最后沒(méi)有辦法恢復(fù)原來(lái)的LCS。

如果需要這個(gè)LCS怎么辦呢？我們得引入一個(gè)前向鏈表，這個(gè)鏈表占用的空間是圖中的藍(lán)格子總數(shù)。所以當(dāng)匹配數(shù)被構(gòu)造滿(mǎn)的時(shí)候，這個(gè)表的大小還是O(nm)的。

廢話(huà)說(shuō)夠了，可以上代碼了

實(shí)現(xiàn)代碼

https://github.com/voidf/pylcs/blob/master/src/main.cpp#L65 本人魔改的pylcs，你可以很容易的把核心邏輯抽出來(lái)拿去交題