動的プログラミングを使用して、指定された文字列内の異なる回文部分文字列を検索します

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃導入＃＃＃

このチュートリアルでは、入力文字列を使用して、考えられるすべての回文部分文字列を検索する方法について説明しました。このタスクのメソッドを実装するには、C プログラミング言語とその関数を使用します。

回文とは、前から後ろ、後ろから前まで同じように読める文字列です。たとえば、Mom は回文文字列です。このチュートリアルでは、文字列を取得し、その中で考えられるすべての回文部分文字列を見つけます。

例 1

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

例 1

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

上記の例では、入力文字列は 7 つの回文部分文字列 ('a'、'b'、'c'、'aa'、'aaa'、'aba'、および 'aca') を生成できます。

例 2

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

例 2

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

上記の例では、入力文字列を使用して取得できる長さ 1 の回文部分文字列は 4 つだけです。入力文字列には繰り返し文字がないため、1 を超える長さの部分文字列はありません。

実装例で使用した関数

size()

-これは、指定された文字列内の文字数を返す文字列のような関数です。パラメータは受け付けません。

＃＃＃文法＃＃＃ リーリー ＃＃＃例＃＃＃ リーリー

• begin()

  -このライブラリ関数は STL で定義されています。マップコンテナの開始反復値を与えます。 構文: マップ名.begin(); 例: mp.begin();

end()

-このライブラリ関数は STL で定義されています。マップコンテナの反復終了値を与えます。

＃＃＃文法＃＃＃ リーリー ＃＃＃例＃＃＃ リーリー

• substr() -入力文字列を使用して部分文字列を生成します。これは、string.h ヘッダー ファイルで定義されます。 2 つのパラメータ (pos、len) を受け入れます。 Pos は部分文字列の開始値、len は部分文字列内の文字数です。

• ＃＃＃文法＃＃＃ リーリー ＃＃＃例＃＃＃ リーリー ＃＃＃アルゴリズム＃＃＃

  指定された文字列を考慮し、その中のすべての回文部分文字列を見つけます。

文字列を反復して、入力文字列のすべての回文部分文字列を検索します。

奇数と偶数の長さの回文部分文字列用に 2 つの配列を作成します。

• 2 つの配列の値をハッシュ マップに格納します。

ハッシュマップに保存されているすべての値を出力します。

部分文字列の数は、ハッシュ マップの長さと同じです。ハッシュ マップを反復処理し、各値を出力します。 for ループを使用してマップ内の各項目にアクセスし、それに関連付けられた値を出力します。最後に、出力される値の数はハッシュ マップのサイズと一致する必要があります。

• ロジック 1 の例

このセクションでは、C プログラミング言語の概念を使用して、上記の例の 1 つを実装します。 main() 関数の入力文字列を考慮し、それを使用して出力を生成します。
• リーリー ＃＃＃出力＃＃＃ リーリー

  ロジック 2 の例

動的プログラミング手法を使用して別の例を実装しています。動的プログラミングでは、時間と複雑さを軽減するためにタスクがサブタスクに分割され、個別に解決されます。
• リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

  このチュートリアルでは、指定された文字列内で考えられるすべての回文部分文字列を見つけるための 2 つのメソッドを開発しました。 2 つの例を使用してタスクを理解し、C プログラミング言語を使用してサンプル コードを作成します。この例を実装するには、ハッシュ マップとベクトルを使用して回文部分文字列を保存します。ハッシュ マップを使用すると、キーと値のペアを照合するのに役立ち、要件に応じて多くのハッシュ関数を使用できます。例を実装するためにいくつかのライブラリ関数も使用しました。

以上が動的プログラミングを使用して、指定された文字列内の異なる回文部分文字列を検索しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。