java - String/Char 配列内のパターンを検索する方法は?

Question

ユーザーからの入力でパターンを探す必要があります。見つかった場合は (開始、終了) 位置を返します。

例えば：-

入力 =A B C D B C A D

探すパターン =D C A

出力 =3,6

パターンは必ずしも連続して発生する必要はありません。

D が入力の先頭にあり、C が中央にあり、A が最後にあるようなものです。- 有効なシナリオ。

私が混乱している2つのこと。

• 入力をどう取るか？配列として？はいの場合、文字列または文字配列として?

• パターンを探すにはどうすればよいですか？

Answer 1

ここでは、入力の形式は問題ではありません。文字列とシーケンスの両方を文字列として使用できます。秘訣は、問題を解決するために使用するアルゴリズムを決定することです。

この場合、貪欲な戦略が機能します。

• S(string) とP(pattern)の 2 つの文字列を読み取ります。
• si文字列pi用とパターン用の2 つのインデックスを作成し、両方をゼロに設定します。
• P.charAt(pi)でS始まる文字を検索しsiます。部分文字列の末尾から文字が見つからない場合si、パターンは存在しません
• P.charAt(pi)それ以外の場合は、 inの最初の出現を取得し、そのインデックスに 1 を加えたS値に設定して、1 つ進めます。sipi
• の最後まで到達したらP完了です
• それ以外の場合は、検索ステップに戻り、パターンが見つかるか文字列がなくなるまで処理を続けます。
• シーケンスのインデックスを出力する必要がある場合は、インデックスの配列を追加し、必要に応じて入力します。配列の長さは の長さと等しくなければなりませんP。

この問題には複数の解決策がある場合があることに注意してください。解決策が存在する場合、このアルゴリズムは、問題を解決する最初の「辞書式」インデックス セットを見つけます。