我可以每次使用兩個字串來做最長的公共子字串。但請考慮以下 3 個字串：
- ABZDCC
- ABZDEC
- EFGHIC
這里我們看到前兩個字串的 lcs 是 ABZD。但是當這將與第三個字串進行比較時，lcs 的長度將為零。但很明顯，lcs 是“C”。如何使用后綴陣列找到n個字串的最長公共子串？
uj5u.com熱心網友回復：
如果您有一個包含每個輸入字串的所有后綴的后綴陣列，那么對于作為所有輸入字串的（連續）子字串的任何字串 X，存在一個連續子陣列，其中每個后綴都以 X 開頭，其中包括一個每個輸入字串的后綴。
此外，如果 X 是最長公共子串，則子陣列可以盡可能小，這樣子陣列中的第一個和最后一個后綴是它們相應輸入字串的唯一后綴。
要找到最長的子串，則：
- 對于后綴陣列中的每個位置，從包含每個字串的后綴的位置開始，找到最小的子陣列。您可以使用遞增的兩個指標技術在每個條目的攤銷常數時間內執行此操作。
- 對于每個這樣的子陣列，找到第一個和最后一個條目的最長公共前綴，這將是子陣列中每個專案的公共前綴。
- 記住你找到的最長公共前綴，它是出現在每個輸入中的最長子串。
uj5u.com熱心網友回復：
當處理兩個以上的字串時，找到兩個最短輸入字串之間的所有公共子字串，然后開始消除未包含在其他輸入字串中的公共子字串。完成后，回傳最長的公共剩余子串。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313547.html
上一篇：如何在3D圖形上找到連接點？