-2

一般的な考え方は、for ループを 2 つ実行し、文字列 1 のすべての文字を実行し、文字列 2 のすべての文字と比較して、すべてが見つかった場合、インクルードを示すことです。そのため、string1 のすべての文字をループして、string2 のすべての文字を比較する必要があります。どのインタビュアーが、それは良い考えではないと言っています。

その後、私はそれを考えています。2 ループしないアイデアを 1 つ生成することはできません。おそらく、最初にstring1からすべての文字を取得し、ツリーに組み込まれた数値であるasc2に変換できます。そのため、string2 と比較すると、検索が非常に高速になります。

それとも、より良いアイデアを持っている人はいますか？

string1 は abc ですが、string2 は cbattt です。これは、すべての文字が string2 に含まれていることを意味します。部分文字列ではなく、

4

2 に答える 2

1

iccthedralが言うように、 Boyer Mooreはおそらくインタビュアーが探していたものです。

于 2012-10-02T00:10:59.047 に答える
1

特定のパターンでテキストを検索すること (パターン マッチング) は、非常によく知られている問題です。既知の解決策:

  1. KMP
  2. 証人のテーブル
  3. ボイヤームーア
  4. サフィックスツリー

すべてのソリューションは、2D パターン マッチング用に一般化できるかどうかなど、いくつかの小さな側面で異なります。前処理が必要な場合、バインドされていないアルファベット、実行時間などについて一般化できる場合...

編集:
ある文字列のすべての文字が他の文字列に含まれているかどうかを知りたい場合は、文字列に特定の文字が含まれているかどうかを示す、アルファベットのサイズのテーブルを使用しないでください。アルファベットが無制限または非常に大きい ( O(1)より大きい) 場合は、ハッシュ テーブルを使用します。

于 2012-10-02T00:18:58.977 に答える