最大の文字列入力長のメモリ使用最適化のための良いテクニック

Question

私は文字列アルゴリズムを設計しており、問題は入力のサイズにあります。定義上、Javaの最大文字列長は2147483647なので、混乱〜2.15x10^9を避けることができます。

nは最大の整数は、上述された定義により（サイズnの列）

入力の長さである

char[n*2 +3]〜2.15x10：

Manacherのアルゴリズムは、定義により、文字の配列を必要とします/ 2 -^9ので、文字の配列は、最大サイズのJavaでmanachersアルゴリズムのこの計算

char [ ~2.15x10^9 ]; 

することができ、inputed文字列にN =（3〜2.15x10^9）の上限を低下させます。正確には正確に1073741822。〜1.1x10^9。

最大長さのchar配列は、（N * 2）+ 32バイト=（〜2.1×10^9 * 2）+ 32バイト=〜4.2x10^9バイト（4.2GBs）

Theresの追加のアレイさまざまなサイズ、セット、およびその他のコレクションから構成されています。私は、これでプログラムが〜30GBsの全体のスペースを占めると信じています。最大1.1×10^9文字の長さであると識別されたアルゴリズムの計算のためのRAMメモリの最大入力のためのものである。

「できるだけ長い文字列入力」と「メモリ管理」の間にも物事を維持するための技術についてアドバイスできますか？ （nは、元の文字列の長さで）あなたは

Answer 1

this articleによると、Manacherアルゴリズムは線形時間で最長の回文構造部分文字列を検索しますありがとうございました。

Here's an implementation in Javaこのアルゴリズムは、メモリ消費量が非常に良いことも示しています（文字列と文字列の2つの配列が必要です）。また、元の文字列の2倍の長さ文字列）。

問題は、元の文字列が非常に長いということですので、あなたが一方

言語の制限、メモリ制限などに達している、あなたのアルファベットは7つの文字で構成されています。あなたの元の文字列の文字がA C T G、文字の区切り文字（例えば、#）と、文字列の開始と終了（例えば、$と@）。つまり、各可能な文字を格納するのに3ビットが必要です。あなたはビット演算子とビットマスクで動作するように喜んでいる場合（longが64ビットで表現されているためです）だから、あなたはlongに21文字を格納することができます。このアプローチはコード化するのがより複雑ですが、メモリの使用量ははるかに少なくなります。

もう1つの解決策は、文字列と配列の代わりに動的構造を使用することです。これらの構造体はかなりのメモリを使用しますが、連続したメモリではないため、整数の最大配列サイズの制限や言語の制限には達しません。suffix treeを使用します。this articleによれば、時間のアプローチ。その記事にはC++の解決策があります。がんばろう！