基於唯一子串的配對字符串

Question

我有兩組字符串，如果可能，我需要在每對中使用相同的子字符串（下面示例中的粗體字;粗體/​​大寫只在這裏強調，沒有辦法通過查看一個列表元素來識別每個列表中唯一的關鍵字符串）。文本的剩餘部分（lorem ipsum）可能對許多元素而言是共同的，或者可能是完全獨特的。

列出一個：

1. 「Lorem存有悲坐阿梅德，直板 consectetur adipisicing ELIT，」
2. 「SED做eiusmod 糖果手杖 tempor incididunt UT labore等dolore 蚤」
3. 「sed do eiusmod tempor HOMER incididunt ut labore et dolore magna」
4. 「Lorem存有悲坐阿梅德，consectetur adipisicing PICKUP TRUCK ELIT，」
5. 「ullamco laboris暫準UT aliquip前EA commodo consequat。 DUIS奧特 「

列出兩種：

1. 」SED做eiusmod tempor incididunt HOMER UT labore等dolore蚤「
2. 」 aliqua。 Ut enim ad minim veniam，CANDY BAR quis nostrud practitation「
3. 」aliqua。 UT enim廣告微量veniam，QUIS nostrud 糖果手杖實習」
4. 「在voluptate velit埃塞cillum dolore reprehenderit」
5. 「irure悲Lorem存有悲坐阿梅德，consectetur adipisicing 皮卡 ELIT，」

從下面的匹配樣本文本是：1-2; 2-3; 3-1;在列表中的一個和元件4在列表2不與任何匹配4-5

元件5

。

Answer 1

如果您處理的數據總量相對較小，那麼已經建議的解決方案（使用.contains()或正則表達式）可能是最實用的。 以下是數據量較大時的一種方法。

解決方案的關鍵部分是使用後綴數組。後綴數組是文本（或多個文本串聯）的所有後綴（字符串結尾，而非語言後綴）的字典順序列表。

在你所描述的例子中，這將涉及構建的兩套只有一個級聯文本的後綴數組。我假設我們爲組2做到這一點，所以我們串接所有句子，採用獨特的分離字符（我選擇了＃字符下方#）：

sed do eiusmod tempor incididunt HOMER ut labore et dolore magna#aliqua. Ut enim ad minim veniam, CANDY BAR quis nostrud exercitation#aliqua. Ut enim ad minim veniam, quis nostrud CANDY CANE exercitation#.... 

接下來，你會構建該字符串的後綴數組，以及最長公共前綴數組（LCP）。如果文本的數量不是非常大，那麼兩種數據結構都可以使用蠻力方法構建。或者，有些庫可以更高效地構建它們，例如jSuffixArrays。

最後，你通過句子重複設置1，並通過啓動相關的標記和搜索集2的後綴數組爲他們（下面空格或標點符號可能隻字）的位置候選的每個句子。 搜索後綴數組當LCP數組可用時，可以在O（n + m）時間（n是集合2的連接字符串的長度，m是要查找的候選字符串的長度）中使用classical search algorithm by Manber and Myers，但如果這仍然太慢，有可用的改進方法，例如由Navarro and Mäkinen 2007描述。

對於您找到的每個匹配項，後綴數組可以隨時提供有關組2中字符串出現頻率以及多少個不同句子的信息。如果需要，我可以在編輯時詳細說明如何對後者進行編輯。

Answer 2

據我所知，你有一個列表中每個列表中唯一的字符串。這些字符串是列表中字符串的一部分（子字符串）。我會創建一個這樣的子字符串列表，然後使用正則表達式比較它們（而不是在這種情況下，您將需要知道啓動索引的Java子字符串）。