1

組み込みメソッドに関連するc＃文字列検索を使用せずにstring.IndexOf機能を実装する必要があります。

このための簡単なアルゴリズムを提案していただけますか。検索には、非常に大きな文字列は含まれません。検索される文字列の最大長を1000文字と見なすことができます。

4

3 に答える 3

4

これは宿題のように聞こえるので、解決策ではなくガイダンスを提供します。ウィキペディアには文字列検索アルゴリズムの概要があります。

http://en.wikipedia.org/wiki/String_searching_algorithm

主題の良い入門書として、ナイーブ文字列検索を実装してみてください。

ある文字列が別の文字列の内部で発生する場所を確認する最も簡単で効率の悪い方法は、文字列が存在する可能性のある各場所を1つずつチェックして、そこにあるかどうかを確認することです。したがって、最初に、干し草の山の最初の文字に針のコピーがあるかどうかを確認します。そうでない場合は、干し草の山の2番目の文字から始まる針のコピーがあるかどうかを確認します。そうでない場合は、3番目の文字から始めます。通常の場合、間違った位置ごとに1つまたは2つの文字を見るだけで、それが間違った位置にあることがわかります。したがって、平均的な場合、これにはO（n + m）ステップが必要です。ここで、nは次の長さです。干し草の山とmは針の長さです。しかし、最悪の場合、「aaaaaaaaab」のような文字列で「aaaab」のような文字列を検索すると、O（nm）ステップが必要になります。

于 2012-07-08T22:59:24.943 に答える
0

他の言語での実装を見てみましたか。例：Java？

これらのソースコードは広く入手可能であり、専門家から学ぶことは常に良い最初のステップです。

于 2012-07-08T22:52:55.143 に答える
0

もう1つの良いガイダンスは、「ある程度の検索を回避できますか？」について考えることです。たとえば、検索文字列がaaaaであり、検索された文字列がaaabaaaabaaaであり、位置[0]から開始する場合でも、位置[1]で検索する必要がありますか？

また、検索文字列の中で照合を開始するのに最適な文字はどれですか？検索文字列がabcdであり、検索文字列がである場合、aababceabcdそれはマッチングループがどのように構造化されるかについてのいくつかの側面を示唆していますか？

于 2012-07-08T23:10:56.660 に答える