私は以下のようなブルートフォース文字列パターン検索アルゴリズムを持っています:
public static int brute(String text,String pattern) {
int n = text.length(); // n is length of text.
int m = pattern.length(); // m is length of pattern
int j;
for(int i=0; i <= (n-m); i++) {
j = 0;
while ((j < m) && (text.charAt(i+j) == pattern.charAt(j)) ) {
j++;
}
if (j == m)
return i; // match at i
}
return -1; // no match
} // end of brute()
ここで上記のアルゴリズムを分析している間、著者は最悪のケースと平均的なケースに言及しました。
私は最悪のシナリオのパフォーマンスを理解しましたが、平均して、作成者はどのようにしてO(m + n)のパフォーマンスを実現しましたか?ここで助けが必要です。
最悪の場合、ブルートフォースパターンマッチングは時間O(mn)で実行されます。
通常のテキストのほとんどの検索の平均はO(m + n)を取りますが、これは非常に高速です。
より平均的なケースの例:T:「文字列検索の例が標準です」P:「ストア」
お時間を割いていただきありがとうございます