問題タブ [subsequence]

lengthの配列が与えられた場合、必要なのは、その特定の配列の長さのサブシーケンスの数を計算nするプログラムを作成することです。m

以下はそれを行うコードです。どうぞ、ご覧ください。

さて、私の質問:値がseqLength毎回減少するのはなぜですか? また、このコードはどのように機能していますか?

私は最長の一般的なサブシーケンス プログラムに取り組んでいますが、何らかの理由で、配列内のすべてを NULL に初期化した後でも、配列がガベージでいっぱいになり続けます。

私の LongestCommonSubsequence 関数では、最初に 2D 配列をハードコードされたサイズで NULL に初期化します。ただし、配列を初期化した後も、まだゴミでいっぱいです。そのため、Traverse 関数をヒットしても、if ステートメントはヒットしません。これらの文字と等しくならないからです。

サブシーケンスの考え方は、この投稿で非常によく説明されています:サブシーケンスの生成

しかし、私は初心者なので、その質問の答えがわかりませんでした。

私が知りたかったのは、関数を使用せずにシンプルで理解しやすい状態に保ちながら、C プログラムをより効率的にすることができるかどうかです。

NUM を 5111 や 100 などの数値として定義すると、一部のサブシーケンスが 2 回表示されることに注意してください。それを修正する簡単な方法はありますか？ありがとう！

私が書いている無関係なプログラムでこの問題に遭遇し、それを解決するのにかなりの時間を費やしました。だったのですが、最後までやりきれませんでした。私のコードは、一部のサブセットのシーケンスのみを解決します。この問題は、おそらく何十年にもわたってさまざまな方法で解決されてきた一般的な数学の問題のようにも感じますが、オンラインでこの特定の問題に関する解決策や実際に何かを見つけるための数学のスキルと用語が不足しています.

より大きな未知の (スーパー?) シーケンスの一部であることがわかっている一連のサブシーケンスがあります。これらのサブシーケンスは順序付けられているため、数学的な意味でのセットではないと思いますが、重複する要素が含まれていないという点で類似しています。master/super/whateversequence についても同様です。(わかりやすくするために、これをスーパーシーケンスと呼びます。)

サブシーケンスにはすべて同じタイプのデータが含まれますが、データはアルファベット順、昇順、またはそのような順序ではありません。ある意味で、データは任意の順序、つまりスーパーシーケンスの順序になっています。それが私が興味を持っていることです。私はこれらの部分配列の未知の超配列を見つけたいと思っています。

簡単にするために、アルファベットの文字を使用してこの問題を解決しようとしましたが、後で必要に応じてコードをリファクタリングできます。明らかに、私はまだこの問題を解決しようとしているので、重複要素を含まないスーパーシーケンスに適した単語を考え出すことから始めました: FLOWCHARTS。

次に、次の 6 つのサブシーケンスを思いつきました。

これが私のシーケンス順序付け方法です：

最後に、私のコードはF,L,O,W,H,C,A,R,T,Sこれらのサブシーケンスのスーパーシーケンスを見つけました。これはかなり近いですが完全ではありません。また、注文方法を複数回実行する必要があるため、思いついた「アルゴリズム」も完璧ではありません。「ルール マップ」とは、キーが、サブシーケンス (したがってスーパーシーケンス) のキー Character の後に来る Character オブジェクトの別のハッシュ マップであるハッシュ マップです。

この種のシーケンス検索を行うために使用できる、ある種の Java ライブラリはありますか? これが何と呼ばれているか、および/または仕事に適したアルゴリズムを見つけるのを手伝ってくれるという点で、誰かが私を正しい方向に向けることができますか?

さらに、私のプログラムの短縮されたコンソール出力:

たとえば、879という数値が与えられた場合、その数値が素数であるかどうか、およびそのすべての数字のサブシーケンスが87、79、8、7、9などを意味する素数であるかどうかをチェックする必要があるプログラムを作成する必要があります。数値が素数かどうかを確認しますが、数値をその数字の部分列に分割する方法がわかりません。

n文字の組み合わせで構成される長さの文字列が与えられますA B D。

例-1:AAAABAAAADADDDDADDDBBBBBBDDDDA

Thresholdof x、指定された部分文字列には、最大長の他の連続した部分文字列を含めることができますx

Ex-2: AEx-1のサブシーケンスのAAAABAAAADA場合、しきい値の (1,11) 境界を持つ正当な部分文字列ですx = 2。

同様に、主な文字列を無視して、 と の部分文字列を個別Aに抽出したいと思います。メイン文字列には、各タイプのサブ文字列が多数存在する場合があります。DB

モデル出力:

Aしきい値より大きい距離が文字列を壊した場合、s間の距離を見つけることによって非効率的な非アルゴリズムの方法を実装しました。と に対してこれを個別に実行する必要がAありDました。これにより、境界領域が重なります。

これを解決するためのより良いアプローチはありますか?

編集-1

有効な部分文字列は任意の長さにできますが、しきい値より大きい他の部分文字列によって汚染されてはなりませんx。つまり、その部分文字列の検索中に、他の文字が含まれていたり、連続してしきい値よりも大きくなったりしAてはなりません。BD

x = 2の検索中AにAABBAAAA, AABDAAAAが有効であるが、 ではない場合AADBDAAA, AABBBAAA。A同様に、D（およびB汚染物質になります）を検索している間。

「Pham Trung」の回答を使用したEDIT-2実装

コード：

出力：

コードは部分文字列の後に1st部分文字列を抽出できません。

O(2^n)Longest Common Subsequence アルゴリズムの再帰関数の複雑さがわかりません。

通常、この表記法はアルゴリズムの基本操作 (この場合は比較) の数と関連付けることができますが、今回は意味がありません。

たとえば、同じ長さの 2 つの文字列があるとし5ます。最悪の場合、再帰関数は251比較を計算します。そして2^5、その値にさえ近くありません。

この関数のアルゴリズムの複雑さを説明できる人はいますか?