サブストリングの重複の検索

Question

重複するサブストリングを見つける効率的な方法はありますか？ここで、重複は、互いに近い2つの同じ部分文字列が重複することなく同じ値を持つことを意味します。たとえば、ソース文字列は次のとおりです。

ABCDDEFGHFGH 

「D」と「FGH」が複製されています。 'F'は2回連続して出現しますが、互いに接近していないので重複しません。私たちのアルゴリズムは['D'、 'FGH']を返します。私はbrute forceメソッドの代わりに優雅なアルゴリズムが存在するかどうかを知りたいですか？

Answer 1

それは線形時間とΘ(n)

Answer 2

非常に効率的ではない宇宙の複雑で検索文字列を提供するために、Suffix Treeを構築している、Longest repeated substring problemに関し、（接尾辞木/配列は非常に大規模な文字列のための優れている）が、非常に短いです正規表現溶液（Cの＃）：

string source = @"ABCDDEFGHFGH"; 

    string[] result = Regex 
    .Matches(source, @"(.+)\1") 
    .OfType<Match>() 
    .Select(match => match.Groups[1].Value) 
    .ToArray(); 

説明

曖昧さの場合には

(.+) - group of any (at least 1) characters 
\1 - the same group (group #1) repeated 

テスト

Console.Write(string.Join(", ", result));  

成果

D, FGH 

、例えば"AAAA"ここで"AA"と"A"を提供することができます。解決策は貪欲に実行されるため、"AA"が返されます。

Answer 3

非常に遅くなる可能性のある正規表現を使用しないと、手を動かす2つのカーソルを使用するのがベストだと思います。アルゴリズムは、以下のJSコードからかなり明らかです。次の値をとりますtsプロセス全体を通じて

function getNborDupes(s){ 
 
    var cl = 0, // cursor left 
 
     cr = 0, // cursor right 
 
     ts = "", // test string 
 
    res = []; // result array 
 
    while (cl < s.length){ 
 
    cr = cl; 
 
    while (++cr < s.length){ 
 
     ts = s.slice(cl,cr); // ts starting from cl to cr (char @ cr excluded) 
 
     
 
     // check ts with subst from cr to cr + ts.length (char @ cr + ts.length excluded) 
 
     // if they match push it to result advance cursors to cl + ts.length and continue 
 
     
 
     ts === s.substr(cr,ts.length) && (res.push(ts), cl = cr += ts.length); 
 
    } 
 
    cl++; 
 
    } 
 
    return res; 
 
} 
 

 
var str = "ABCDDEFGHFGH"; 
 
console.log(getNborDupes(str));

。

A 
AB 
ABC 
ABCD 
ABCDD 
ABCDDE 
ABCDDEF 
ABCDDEFG 
ABCDDEFGH 
ABCDDEFGHF 
ABCDDEFGHFG 
B 
BC 
BCD 
BCDD 
BCDDE 
BCDDEF 
BCDDEFG 
BCDDEFGH 
BCDDEFGHF 
BCDDEFGHFG 
C 
CD 
CDD 
CDDE 
CDDEF 
CDDEFG 
CDDEFGH 
CDDEFGHF 
CDDEFGHFG 
D 
E 
EF 
EFG 
EFGH 
EFGHF 
EFGHFG 
F 
FG 
FGH 

cl = cr += ts.length一部が再起動し、一致する部分文字列の前または後からの検索をするか否かを判断するけど。現在のところ、上記のコードです。 "ABABABAB"入力は["AB","AB"]を返しますが、cr = cl += ts.lengthにすると結果は["AB", "AB", "AB"]になるはずです。