指定された文字列に長さ 2 以上の繰り返しサブシーケンスがあるかどうかを調べる C++ プログラム

指定された文字列で、その文字列内で繰り返される長さ 2 以上の部分シーケンスを見つけます。サブシーケンス要素番号のインデックスを同じ順序にすることはできません。

リーリー

このアプローチがさまざまな状況でどのように機能するかを理解するために、以下のいくつかの例を見てみましょう -

例 1 - str = "PNDPNSP"

説明 -ここでは、文字列内に繰り返しのサブシーケンス「PN」があるため、答えは真です。

例 2 - str = "PPND"

説明 - ここでは、文字列内に長さ 2 以上の繰り返し部分シーケンスがないため、答えは間違っています。

例 3 − str = "PPNP"

説明 - ここでは、「PP」インデックス 0 と 1、「PP」インデックス 1 と 3 が存在し、使用される「PP」のサブシーケンス インデックスの順序が異なるため、答えは正しいです。 (0 から始まるインデックス)

ブルート フォース アプローチ

の中国語訳は次のとおりです。

ブルート フォース アプローチ

このメソッドは、長さ 2 (最小長) のすべての可能なサブシーケンスを生成し、見つかったサブシーケンスでそのサブシーケンスが既に存在しているかどうかを確認します。サブシーケンスが既に存在する場合は true を返し、プログラムを終了します。それ以外の場合、反復の完了後、何も見つからなかった場合は false を返します。

最悪の場合、このサブシーケンスは存在しない可能性があり、考えられるすべての結果を生成することになります。

2 つの長さのサブシーケンスを作成して保存します。したがって、計算されたサブシーケンスをハッシュして O(1) の挿入と検索を達成すると仮定すると、これは O(n^2) になります。サブシーケンスの合計も O(n^2) なので、記憶領域も同様です。

変更された最長共通部分列 (LCS)

LCS アルゴリズムは、2 つの文字列内の最長の共通部分シーケンスを見つけます。これは、2 次元行列の反復法を使用する標準的な動的プログラミング手法です。時間計算量は O(n^2) です。変更されたメソッドでは、指定された文字列自体のみを検索します。ただし、現在位置のインデックスが同じでないかどうかも確認します。

＃＃＃例＃＃＃

長さ 2 以上の繰り返しサブシーケンスの検索を容易にする、修正された最長共通部分シーケンス アルゴリズムを実装するには、以下の C コードを参照してください。 -

リーリー ＃＃＃出力＃＃＃ リーリー

もちろん、時間と空間の複雑さは O(n^2) ですが、最初の方法よりも、よりエレガントで、O(1) ハッシュを生成するのが簡単です。

改善されたソリューション

このアプローチでは、前のアプローチに基づいていくつかの観察を試みます。

観察 1

-文字が 2 回以上出現する場合、答えは常に true です。理由を見てみましょう?

例 - 文字列 str = "AVHJFBABVNHFA" の 0、6、および 12 の位置に「AAA」があります。それで インデックス 0 と 6 に「AA」をサブシーケンスとして、インデックス 6 と 12 に「AA」をサブシーケンスとして含めることができます。 別のものとして。

観察 2 - 文字が 1 回だけ繰り返される場合、その文字は結果に寄与しません。 サブシーケンスは最大でも 1 つのサブシーケンスでしか使用できないためです。それはうまくいきません 少なくとも 2 つのサブシーケンスが必要であるためです。したがって、すべての文字を削除または無視できます 同時に起こりました。

観察 3 -文字列が回文であり、最初の 2 つの観察が当てはまる場合、答えは次のようになります。 文字列の長さが奇数でない限り、常に false です。理由を見てみましょう?

例 - 文字列 str = "PNDDNP"

説明 - 文字の順序が整っていないため、文字を見つけることはできません。 サブシーケンスの順序は同じであるため、これは不可能です。

＃＃＃例＃＃＃

上記の 3 つの観察結果すべてに基づいて、文字列内に 1 回出現するすべての文字を削除し、特定の文字が 2 回以上出現するかどうか、または文字列が回文でないかどうかを確認すれば、答えは正しいと結論付けます。 。 C で実装された改良されたソリューションを見てみましょう - リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃ 私たちは、観察とハッシュを使用することがこの問題を解決する最良の方法であると結論付けました。時間計算量は O(n) です。スペースの複雑さも O(n) のオーダーであり、新しい文字列と定数 26 文字のハッシュが作成されます。

以上が指定された文字列に長さ 2 以上の繰り返しサブシーケンスがあるかどうかを調べる C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。