上期，我們主要講解了后綴數(shù)組在單字符串問(wèn)題上的應(yīng)用。在多字符串問(wèn)題上，后綴數(shù)組是否仍然有優(yōu)秀的表現(xiàn)呢？
答案顯然是肯定的。

最長(zhǎng)公共子串

Problem：給定兩個(gè)字符串S和T，求這兩個(gè)字符串的最長(zhǎng)公共子串。

Solution：容易發(fā)現(xiàn)，一個(gè)字符串的子串，一定是該字符串的每個(gè)后綴的前綴。所以，求兩個(gè)字符串的最長(zhǎng)公共子串，只需要找這兩個(gè)字符串的后綴的最長(zhǎng)公共前綴就行了。

但是，問(wèn)題在于如何對(duì)兩個(gè)字符串使用后綴數(shù)組呢？

這里有一個(gè)小技巧。我們可以用一個(gè)在兩個(gè)字符串中都沒(méi)有出現(xiàn)的字符（例如特殊字符等）將這兩個(gè)字符串連接到一起（這里是為了對(duì)新字符串進(jìn)行截?cái)啵缦聢D所示：

Example

這樣我們就把問(wèn)題轉(zhuǎn)化成：給定一個(gè)字符串，求這個(gè)字符串前一部分的后綴和后一部分的后綴的最長(zhǎng)公共前綴的長(zhǎng)度。由height數(shù)組的性質(zhì)，我們只需判斷相鄰的兩個(gè)后綴是否屬于新字符串的不同部分。如果是，就能用該位置的height來(lái)更新答案。下面是一個(gè)例子：

Example

為什么不用把前半部分的后綴和后半部分的后綴兩兩求最長(zhǎng)公共前綴呢？我們知道從一個(gè)后綴a開(kāi)始，往后求a和任意一個(gè)后綴的最長(zhǎng)公共前綴（設(shè)長(zhǎng)度為L(zhǎng)），L會(huì)小于之間任何一個(gè)height的值。所以，當(dāng)一個(gè)后綴向后匹配超過(guò)一個(gè)后綴是沒(méi)有必要的。

長(zhǎng)度不小于k的公共子串的個(gè)數(shù)

Problem：給定兩個(gè)字符串S和T，求這兩個(gè)字符串中長(zhǎng)度不小于k的公共子串的個(gè)數(shù)。其中，公共子串可以相同。

Solution：先考慮一個(gè)暴力的方法：先將字符串S和T用一個(gè)沒(méi)出現(xiàn)過(guò)的字符連接起來(lái)得到新字符串A，然后求A的后綴數(shù)組，對(duì)于每一個(gè)S的后綴（即A的前半部分的后綴），我們可以統(tǒng)計(jì)它和每一個(gè)T的后綴的最長(zhǎng)公共前綴。

這樣的復(fù)雜度極高，那么有沒(méi)有什么優(yōu)化的方法呢？

我們可以嘗試對(duì)A的后綴數(shù)組進(jìn)行順序遍歷，遍歷到一個(gè)S的后綴時(shí)，統(tǒng)計(jì)這個(gè)后綴與之前出現(xiàn)過(guò)的T的后綴的最長(zhǎng)公共前綴?？紤]height數(shù)組的性質(zhì)，對(duì)于一個(gè)后綴sa[j]，sa[i] (1<=i<j) 和sa[j]的最長(zhǎng)公共前綴隨i的增大而增大。

所以，我們可以用一個(gè)數(shù)組q來(lái)維護(hù)處理到sa[j]時(shí)，出現(xiàn)過(guò)的T的后綴與sa[j]的最長(zhǎng)公共前綴。通過(guò)前面的分析，我們知道數(shù)組q是單調(diào)遞增的。所以，每次新掃過(guò)一個(gè)后綴，我們可以用二分的方法來(lái)更新數(shù)組q中的值。如果當(dāng)前這個(gè)后綴是T的后綴，那么我們就把這個(gè)后綴加入數(shù)組q。否則就計(jì)算數(shù)組q中每一個(gè)后綴與當(dāng)前后綴的最長(zhǎng)公共前綴（即q數(shù)組中每一個(gè)元素的和）。

總結(jié)

我們介紹了后綴數(shù)組在兩個(gè)字符串問(wèn)題上的應(yīng)用。多個(gè)字符串與之類(lèi)似，我們只需要把多個(gè)字符串用沒(méi)出現(xiàn)過(guò)的字符連接起來(lái)，求解后綴數(shù)組，然后依題意來(lái)判斷即可。

【信息學(xué)競(jìng)賽從入門(mén)到巔峰】，一個(gè)專(zhuān)注于分享OI/ACM常用算法及知識(shí)的公眾號(hào)。