☰

java indexof(String str) メソッドの複雑さ [重複] 質問する

tag-icon • tag-icon java algorithm
java indexof(String str) メソッドの複雑さ [重複] 質問する

重複の可能性あり:
String.indexof()関数呼び出しのコスト/複雑さはどれくらいですか

java indexof(String str) メソッドの複雑さはどの程度ですか。つまり、線形時間で実行される KMP のような文字列マッチング アルゴリズムがあります。非常に大きな文字列内の大きな部分文字列を検索するシステムを実装しているのですが、java indexof(String str) メソッドを使用できますか、それとも KMP を実装する必要がありますか。

ベストアンサー1

Javaの複雑さ実装は、検索文字列とパターンの長さですindexOf。O(m*n)nm

複雑さを改善するためにできることは、例えば、ボイヤー・モアパターンに一致しない文字列の論理部分の比較をインテリジェントにスキップするアルゴリズム。

おすすめ記事