最長非重疊子字符串

我想知道是否有人知道最長重複非重疊子字符串的（最佳？）算法。最長非重疊子字符串

例如，串

ABADZEDGBADEZ

最長的重複將是「壞」的。順便說一句，如果沒有這樣的結果，算法應該警告已經發生了這樣的事情。我的猜測是這涉及到後綴樹。

我相信這一定已經存在。謝謝您的幫助！

來源

2009-08-24 Brandon Pelfrey

只是curious-有什麼業務應用爲了這？ – Beth 2009-08-24 17:42:30

這不是一個商業應用程序。這與在歌曲中找到主題有關，並且此時更多的是一個古董，直到我得到一個涉及此項目的項目。 =] – 2009-08-24 17:44:27

由於您將此應用於音樂，因此您可能不會尋找100％的匹配;預計從主題的一個實例到另一個實例的預期差異。你可以試着查找基因序列分析算法 - 這裏有很多這樣的東西。嘗試BLAST或其他比對算法。您也可以嘗試WinEPI算法家族以及此特定結果集的各種前綴樹實現（這些結果允許在子字符串中存在空位;例如，ABCID和AFBCD都包含ABCD）。實際上我有一篇關於算法的論文，如果您有興趣，可能值得一看;我需要獲得授權，請告訴我。

請注意，對於大型數據集來說，這實際上是一個非常複雜的主題（爲了高效）。

來源：一年或兩年研究可比（主題檢測）主題。

來源

2009-08-24 17:46:10

如果您可以授予我訪問權限，將不勝感激！ – 2009-08-24 18:04:07

我認爲他將這個應用於歌詞，所以我認爲他正在尋找100％的比賽。 – las3rjock 2009-08-24 18:06:09

@Brandon - 我已經申請了許可，我會看看我能做些什麼。 @ las3rjock - 不是。例如：我是一個傻男人我是傻，男人實例主題：過去式的愚蠢。字符串不完全匹配。另外，很多歌詞有不同的標點符號和不一樣的。所以我不確定他是否在尋找完全匹配。 – 2009-08-24 18:08:30

Suffix array是一個很好的解決這個問題的數據結構。

Jon Bentley在Programming Pearls中有這個問題的解決方案。

來源

2009-08-24 17:54:11

在編程珍珠的地方？ – 2009-08-24 20:47:12

@Emil H，** 15.2短語** – 2009-08-25 04:16:35

@Nick我不認爲在編程珍珠相同的解決方案可直接應用於此。「BANANA」的例子給出了兩次出現的「ANA」，並且因此與OP所述的條件相反，因此是重疊的。對於非重疊條件可能需要進行一些修改。你說什麼？ – 2012-11-11 10:29:35

一個簡單的算法是做到這一點：

創建表示字符串切片的數據結構;根據語言實施比較/排序
創建一個以[first-character，last-character]，[second-character，last-character]開頭的字符串的每個片段的列表，直到[last-character，最後字符]
對此列表進行排序 - O（n log n）
這將所有帶有公共前綴的字符串切片放在一起。然後，您可以遍歷列表，比較每一對，看看它們在開始時共享了多少個字符，並且如果它大於最大值，則記下它並將其設置爲新的最大值（作爲新的最大值）

（As剛剛發佈的其他回覆表明，我在這裏描述了一個後綴數組。）

來源

2009-08-24 17:55:06

這仍然相當強悍。我想知道是否有一個更優雅的方法？我相信基於樹的方法可以保留結構信息，並提供某種可以快速遍歷以提供最長信息的深度信息。 – 2009-08-24 18:00:06

使用適當的排序 - 請參閱後綴數組維基百科文章 - 運行時間在最差情況下爲O（n log n），通常更好。迭代是O（n），所以主要是排序成本。至少明顯的蠻力將是O（n^2）（比較每個可能的對）。構建樹木可能會花費更多的內存，這會對性能產生不利的現實影響（考慮緩存等）。 – 2009-08-24 18:06:48

好的，這裏有一個瘋狂的想法。

創建一個函數，確定O（n）（其中n是文本的長度）中是否存在長度爲k的循環子字符串。這可以通過使用滾動散列（請參閱維基百科Rabin-Karp String Matching Algorithm）以線性時間生成所有n散列並使用散列表/ BST（或地圖或字典或任何您的語言稱爲它）來存儲相應的子字符串位置。在將當前散列插入數據結構之前，我們先檢查一下是否看過。如果之前已經看到過，我們只需查找生成此散列的索引，並查看相應的子字符串是否爲非重疊匹配。

現在，我們可以發現在O（n）的時間A K長度字符串，我們只需運行一個二進制搜索找到我們可以用我們的功能找到一個不重疊的子字符串匹配最大ķ。在Python

代碼如下

A=23 
MOD=10007 # use a random value in the real world 

def hsh(text): 
    return sum([ord(c)*A**(len(text)-i-1) for i,c in enumerate(text)])%MOD 

def k_substring(text, k): 
    substrings={} 
    cur=hsh(text[:k]) 
    pwr=(A**(k-1))%MOD 
    substrings[cur]=[0] 
    for i in xrange(k,len(text)): 
     to_remove=(ord(text[i-k])*pwr)%MOD 
     to_add=ord(text[i]) 
     cur-=to_remove 
     if cur<0: 
      cur+=MOD 
     cur=(cur*A)%MOD 
     cur=(cur+to_add)%MOD 
     if cur in substrings: 
      lst=substrings[cur] 
      for index in lst: 
       if index+k<=i-k+1 and text[index:index+k]==text[i-k+1:i+1]: 
        return index 
      lst.append(i-k+1) 
     else: 
      substrings[cur]=[i-k+1] 
    return -1 

def longest_substring(text): 
    hi,lo=len(text),0 
    while hi>lo: 
     mid=(hi+lo+1)>>1 
     if k_substring(text,mid)==-1: 
      hi=mid-1 
     else: 
      lo=mid 
    index=k_substring(text,lo) 
    return text[index:index+lo]

（很抱歉，如果這是目前還不清楚。這是上午6:30在這裏，我真的要回去睡覺了:)）

來源

2009-08-24 23:34:51 MAK

最長非重疊子字符串

回答

相關問題