suffix-array

2熱

1答えて

文字列内の各サフィックスの発生数を調べるにはどうすればよいですか？

オリジナルの文字列内で、文字列の各接尾辞が何回出現するかをO（nlogn）またはO（n）の時間で検索したいと考えています。 たとえば、文字列abaの場合、接尾辞aが2回​​表示され、baが一度表示され、abaが一度表示されます。

c++ string algorithm hash suffix-array 2016-10-15

---

-3熱

1答えて

サフィックスツリーによってO（n）時間に宿題を解決するアルゴリズムを実装する方法は？

私はバイオインフォマティクスに質問があります。サフィックスツリー構造で解決できます。 文字列S = S [1 ... n]と番号kが与えられた場合、S内で発生するSの最小の部分文字列が存在する場合、それを正確にk回探したいと考えます。 O（n）時間にこの問題を解決するには？

algorithm data-structures bioinformatics string-matching suffix-array 2016-05-19

---

0熱

1答えて

時間の複雑さに対するUkkonenのアルゴリズムを用いたKnuth-Morris-Pratt（KMP）と接尾辞木の違い。

Ukkonenのアルゴリズムを使用して、最長共通部分文字列、最長パラドーム部分文字列、最長繰り返し部分文字列、すべてのパターンと部分文字列検索をKMPとサフィックスツリーで検索できますか？もしそうなら、両方のアルゴリズムは線形時間の複雑さを持つので、どちらを使うべきですか？

string algorithm time-complexity suffix-array knuth-morris-pratt 2016-09-05

---

-1熱

1答えて

接尾辞配列の構築

私はこのlinkから接尾辞配列の構築を学んでいます。ここで は、私はC++からJavaの class Entry implements Comparable<Entry> { int [] nr = new int[2]; int p=0; public int compareTo(Entry that){ if (this.nr[0] == that

java arrays suffix-array 2016-04-12

---

17熱

2答えて

接尾辞配列対接尾辞木

接尾辞ツリーが拡張接尾辞配列よりも優れている場合、私はちょっと知りたいです。 Replacing suffix trees with enhanced suffix arraysを読んだ後、私はもうサフィックスツリーを使用する理由はありません。いくつかのメソッドは複雑になることがありますが、接尾辞配列ですべてを行うことができます。接尾辞ツリーで何ができ、同じ複雑さが必要ですが、メモリは少なくて済みます

algorithm time-complexity suffix-tree space-complexity suffix-array 2012-06-25

---

5熱

1答えて

複数の文字列の最長共通部分を計算するために、我々は接尾辞リンク（<a href="http://www-igm.univ-mlv.fr/~lecroq/articles/awoca2000.pdf" rel="nofollow">paper here</a>）と因子のOracleを使用することはできLRS配列

で強化因子Oracleを使用して複数の文字列の最長共通部分を探しますか？ここでは、サブは、元の文字列の一部を意味します。たとえば、 "abc"は "ffabcgg"の部分文字列ですが、 "abg"はそうではありません。 私は2つの文字列s1とs2の最大長の共通部分文字列を計算する方法を見つけました。 2つの文字列を連結していない文字、例えば '$'を使用して動作します。その後、長さi >= |s1

algorithm automata suffix-tree suffix-array 2012-08-14

---

0熱

1答えて

サフィックス配列がサフィックスツリーよりも少ないスペースを使用する理由は何ですか？

私は私のプロジェクトのための接尾辞配列とサフィックスツリーについて研究しています。ユハKarkkainenとピーターによる1993年 「単純な線形作業接尾辞配列の構築」 - Manberとマイヤーズ： 「オンライン文字列検索のための新しい方法接尾辞配列：」のようないくつかの論文で 「接尾辞配列の利点はサフィックスツリーより少ないスペースを使用して」： - サンダース2003 は、著者がいることを言

data-structures suffix-tree suffix-array 2017-12-08

---

0熱

1答えて

2つの接尾辞配列を作成しようとするとEXC_BAD_ACCESSエラーが発生するのはなぜですか？

私の仕事は、接尾辞配列を使って2つのtxtファイルで最も長い共通部分文字列を見つけることです。私は次のように行った： #include <iostream> #include <cstring> #include <algorithm> #include <fstream> int main() { char* charArrayA = charArrayFromTxtFile

c++ dynamic-memory-allocation suffix-array 2017-12-13

---

0熱

2答えて

少なくともk個のオカレンスを持つ最長繰り返し部分文字列

最長繰り返し部分文字列を見つけるためのアルゴリズムは、次のように書かれています 1)build the suffix tree 2)find the deepest internal node with at least k leaf children しかし、なぜこのアルゴリズムが正しいのか理解できません。アルゴリズムでは、O（n）に繰り返し部分文字列があると言いますが、nは部分文字列の長さです

string algorithm suffix-tree suffix-array longest-substring 2016-11-15

---