BruteForce

2535 ワード
python algorithm テキストリンク

BruteForce

  • は、本文文字列を逐次巡回する、比較モード中の文字を逐次比較するように動作する
    • .
    最悪の場合、時間的複雑度は
  • であり、テキストのすべての位置でモードを比較する必要があるため、O(MN)
    • である.
    def BruteForce2(p,t) :
    n = len(t)
    m = len(t)
    cnt = 0
    for i in range(n-m + 1) :
        match = 0
        for j in range(m) :
            if t[i+j] != p[j]:
                break
            else :
                match +=1
        if match == m :
            cnt += 1

    return cnt
  • 長さ-パターン+1(インデックスエラー防止)
  • モードを迂回、テキスト中のi+jがモード中のjと異なる場合は、入力を停止する
    • である.
  • に一致する場合、
    • に進む
  • j=m-1=
  • は、
    • と一致するものとみなす.
    KMP
    location.hrefジャンプテスト