上期庄涡，我們主要講解了后綴數(shù)組在單字符串問題上的應(yīng)用。在多字符串問題上搬设，后綴數(shù)組是否仍然有優(yōu)秀的表現(xiàn)呢穴店？
答案顯然是肯定的。
最長公共子串
Problem：給定兩個字符串S和T拿穴，求這兩個字符串的最長公共子串泣洞。
Solution：容易發(fā)現(xiàn)，一個字符串的子串默色，一定是該字符串的每個后綴的前綴球凰。所以，求兩個字符串的最長公共子串，只需要找這兩個字符串的后綴的最長公共前綴就行了呕诉。
但是缘厢，問題在于如何對兩個字符串使用后綴數(shù)組呢？
這里有一個小技巧甩挫。我們可以用一個在兩個字符串中都沒有出現(xiàn)的字符（例如特殊字符等）將這兩個字符串連接到一起（這里是為了對新字符串進(jìn)行截?cái)啵┨颍缦聢D所示：
這樣我們就把問題轉(zhuǎn)化成：給定一個字符串，求這個字符串前一部分的后綴和后一部分的后綴的最長公共前綴的長度伊者。由height數(shù)組的性質(zhì)英遭，我們只需判斷相鄰的兩個后綴是否屬于新字符串的不同部分。如果是亦渗，就能用該位置的height來更新答案挖诸。下面是一個例子：
為什么不用把前半部分的后綴和后半部分的后綴兩兩求最長公共前綴呢？我們知道從一個后綴a開始央碟，往后求a和任意一個后綴的最長公共前綴（設(shè)長度為L）税灌，L會小于之間任何一個height的值均函。所以亿虽，當(dāng)一個后綴向后匹配超過一個后綴是沒有必要的。
長度不小于k的公共子串的個數(shù)
Problem：給定兩個字符串S和T苞也，求這兩個字符串中長度不小于k的公共子串的個數(shù)洛勉。其中，公共子串可以相同如迟。
Solution：先考慮一個暴力的方法：先將字符串S和T用一個沒出現(xiàn)過的字符連接起來得到新字符串A收毫，然后求A的后綴數(shù)組，對于每一個S的后綴（即A的前半部分的后綴）殷勘，我們可以統(tǒng)計(jì)它和每一個T的后綴的最長公共前綴此再。
這樣的復(fù)雜度極高，那么有沒有什么優(yōu)化的方法呢玲销？
我們可以嘗試對A的后綴數(shù)組進(jìn)行順序遍歷输拇，遍歷到一個S的后綴時，統(tǒng)計(jì)這個后綴與之前出現(xiàn)過的T的后綴的最長公共前綴贤斜〔叻停考慮height數(shù)組的性質(zhì)，對于一個后綴sa[j]瘩绒，sa[i] (1<=i<j) 和sa[j]的最長公共前綴隨i的增大而增大猴抹。
所以，我們可以用一個數(shù)組q來維護(hù)處理到sa[j]時锁荔，出現(xiàn)過的T的后綴與sa[j]的最長公共前綴蟀给。通過前面的分析，我們知道數(shù)組q是單調(diào)遞增的。所以跋理，每次新掃過一個后綴拍霜，我們可以用二分的方法來更新數(shù)組q中的值。如果當(dāng)前這個后綴是T的后綴薪介，那么我們就把這個后綴加入數(shù)組q祠饺。否則就計(jì)算數(shù)組q中每一個后綴與當(dāng)前后綴的最長公共前綴（即q數(shù)組中每一個元素的和）。
總結(jié)
我們介紹了后綴數(shù)組在兩個字符串問題上的應(yīng)用。多個字符串與之類似，我們只需要把多個字符串用沒出現(xiàn)過的字符連接起來生闲，求解后綴數(shù)組叠必，然后依題意來判斷即可。
【信息學(xué)競賽從入門到巔峰】式廷，一個專注于分享OI/ACM常用算法及知識的公眾號。
