アルゴリズム設計-リピートされた文字列のサブストリングLRSを探しています.

2817 ワード

java 文字列アルゴリズム

読書ノートですが、転載の場合は出典を明記してください.http://segmentfault.com/blog/exploring/手を伸ばして党を複製することを拒否する
問題の説明:
まずこれは単一文字列の問題です.サブ文字列Rは、文字列Lに少なくとも2回現れ、RはLの繰り返しサブ列と称される.たとえば、文字列abcdeabcdのLRSの長さは2であり、LRSはabcdである.

Longest Repeated Substring in GEEKSFORGEEKS is: GEEKS
Longest Repeated Substring in AAAAAAAAAA is: AAAAAAAAA
Longest Repeated Substring in ABCDEFG is: No repeated substring
Longest Repeated Substring in ABABABA is: ABABA
Longest Repeated Substring in ATCGATCGA is: ATCGA
Longest Repeated Substring in banana is: ana
Longest Repeated Substring in abcpqrabpqpq is: ab (pq is another LRS here)

いくつかの定義:
サフィックス:サフィックスとは、ある位置iから始まる列の最後までの特別な子列のことです.文字列rのi番目の文字から始まるサフィックスはSuffix(i)であり、Suffix(i)=r[i..len(r)]である.
サフィックス配列:サフィックス配列SAは、1.nのある配列SA[1]，SA[2]，...，SA[n]，を保存し、

Suffix(SA[i]) < Suffix(SA[i+1])，1≤i
     S  n                              SA  。

を保証する1次元配列である.
文字列の大きさの比較:文字列の大きさの比較は“辞書の順序”を指して、つまり2つの文字列u、vについてです.u[i]とv[i]を1から順番に比較し、u[i]=v[i]を1とすると、u[i]v[i]を1とすると、u>v(つまりv len(u)またはi>len(v)と比較できない場合、len(u)vとする.
方法1:O(n^3)直接サブストリングとサブストリングの比較は、文字列abcdabdのようなすべての文字列を確認し、最初の要素aを遍歴し、第二の要素から探し始め、あるものが彼と同じであることを発見し、ラベリングk＋＋＋＋、j＋＋＋＋＋＋…を開始し、そして等しいサブストリングの長さを記録し、そして第二の要素bを遍歴して開始する.


public class LRS {
    private static int statLen(String X, int k, int j) {
        int cur_len = 0;

        while(k

方法2
拡張子配列を使用して時間の複雑さを低減することは、O(n^2)の拡張子配列の定義である.1つの文字列は、次の図のように、各拡張子列の開始アドレスを定義している.
Treesetを使ってサフィックス配列を保存できるString達.
アルゴリズムの主要思想

は、を利用して、可能なすべてのサブストリングの開始アドレスを記録することを実現し、(拡張子配列を使用する利点は、すべての開始位置の同じ文字を一緒に置くことであり、第2のポインタを移動させずに、どの文字が第1のポインタが指す文字と同じで、1つのnの次元を低くする複雑さを探すことである)

を使用しない.

はその後、並べ替えを利用して、スタートアドレスが一致する文字を一緒に置く.このように暴力法において、次の同じ要素を移動jによって制御するプロセスを簡略化する.同じ文字が隣の位置に置かれているので、拡張配列の要素から始まるサブストリングの2つの比較で、重複するサブストリングの長さが分かります.
For example

たとえば上のbanaの例はbanaの一回の循環を巡回して、拡張配列を得て上の図のようです.

その後、並べ替えを行います.

です.
このとき、拡張子配列を巡回して、隣接するサブストリングごとに、2つのサブストリングの共通長さを計算します.C++言語では、拡張配列が記録されています.は、1つの文字ポインタで、サブストリングの先頭文字を指します.Java言語は、ポインタがないので、実現するのが面倒くさいかもしれません.他の人の1つのインプリメンテーションは、Treesetを利用して、直接にすべてのサフィックス配列に対応するサブストリングを記録しますが、空間的なオーバーヘッドが大きすぎると感じます.
複雑度の分析:
最初のオリジナル配列を遍歴して、拡張配列を得る複雑さはO(n)であり、拡張配列の順序付けの複雑さはO(nlogn)であり、最長の反復子列を計算し、拡張子配列O(n)を遍歴し、2つの隣接要素ごとの比較O(n)であるため、複雑度はO(n)＋O(n^2)＝O(n^2)であり、暴力法(O)を比較している.複雑度が小さいのは、拡張子配列というデータ構造を利用して、各サブストリングの開始位置をキャッシュし、順序付けによって、暴力法においてjによる位置付けを回避するための、もう一つの循環があるからです.

よく使うjavascript