【アルゴリズム(JS実装)】Naive String Pattern Matching (Brute Force Approach)

　どうも、わくばです！

　今日からPattern Searchingに入りたいと思います。KMP AlgorithmやBoyer Moore Algorithmなどちょっと耳にしたことのある仰々しい名前のアルゴリズムが待っているジャンルなのでちょっと怖いです(小並感)。

　まずはNaive String Pattern Matchingです。Naiveとってことは一番基本的ということなんでしょうか。確かにKMPなどもっと凝ったものがあるのでそれと比較してNaiveってことなんですかね。

　シンプルな文字マッチのアルゴリズムです。

コードは以下のようになりました。

const naiveStrMatching = (pattern, text) => {
    const result = [];
    //textの中のi番目からpatternと比較を開始
    for (let i=0; i <=text.length - pattern.length; i++) {
        //jはpatternのインデックス
        let j=0;
        while (j < pattern.length) {
            //textとpatternが一致しなかって時点で
            //i番目から始まる比較は終了する
            if (text[i + j] != pattern[j] ) {
                break;
            }
            //patternと一致する限りカウントしていく
            j++;
        }
        //ｊでカウントした値とpatternが一致すれば
        //patternがピッタリ一致したことになるので
        //そのスタートであるiを返す。
        if (j===pattern.length) {
            result.push(i);
        }
    } 
    return result;
} ;

 　whileとif breakの使い方が独特だなと感じました。ループを抜ける条件をより細かく指定できます。

　時間計算量はpatternのサイズをm、textのサイズをnとすると\(O(m\cdot (n-m))\)になります

以上になります。アルゴリズムって無限にあって、競プロerの方々は本当にすごいですね。時間制限あったら絶対ムリです笑

　では。