動機

現在重看一遍還是很複雜

BoyerMoore

從後面開始比

  • 不符合的字元: 壞字元
  • 已經比過的後綴: 好後綴

mismatch時就是看 壞字元 或是 好後綴 誰跳得比較多，就選哪一個

下面

  • bad是下一個壞字元出現的位置，所以要看與最後一個的距離決定跳多遠
  • good就直接是要跳多遠
int BoyerMoore(char p[], char s[]) {
    int ALPHABET_SIZE = 256, len = strlen(p);
    int bad[ALPHABET_SIZE+5], good[len+5];
    getBadChar(bad, ALPHABET_SIZE, p);
    getGoodSuffix(good, p);
    int j = 0, i;
    while(j <= strlen(s) - len) {
        for(i = len - 1; i >= 0 && p[i] == s[i+j]; --i) {
            ;
        }
        if(i < 0) {
            return j;
        }
        else {
            j += max(bad[s[i+j]]-(len-1-i), good[i]);
        }
    }

    return -1;
}

壞字元

遇到mismatch就往後跳到下一個有一樣字的

inline void getBadChar(int bad[], int ALPHABET_SIZE, char pattern[]) {
    int len = strlen(pattern);
    for(int i = 0; i < ALPHABET_SIZE; ++i) {
        bad[i] = len;
    }
    for(int i = 0; i < len; ++i) {
        bad[pattern[i]] = len - 1 - i;
    }
}

好後綴

  1. 如果前面有完全一樣的後綴，直接跳過去
  2. 如果從部分後綴與從開頭開始的一樣，直接跳過去
  3. 都沒有，就整個跳掉

這裡的跳掉就是從當前的點向後移動，所以下面good最後的內容都是len - 1 - i 也就是當前與最後的距離

inline void getGoodSuffix(int good[], char pattern[]) {
    int len = strlen(pattern);
    int suffix[len]; // 這是 以 i 為終點往前看有多長是與從最後往前看一樣的長度
    // a b c d f b c d
    // 0 0 0 3 0 0 0 8
    getSuffix(suffix, pattern);
    // case 3
    // 假設都沒有好後綴，就把整條跳過去
    for(int i = 0; i < len; ++i) {
        good[i] = len;
    }
    // case 2
    // 有 0 ~ j的後綴 與 當前的部分後綴 相同
    for(int i = len-1, j = 0; i >= 0; --i) {
        if(suffix[i] == i + 1) {
            for(; j < len - 1 - i; ++j) {
                if(good[j] == len) {
                    good[j] = len - 1 - i; // 把後面都吃掉
                }
            }
        }
    }
    // case 1
    // 有一樣的後綴，整個跳過去
    for(int i = 0; i <= len-2; ++i) {
        good[len-1-suffix[i]] = len - 1 - i;
    }
}

suffix

最簡單的就是每一次都從後面開始比

inline void getSuffix(int suffix[], char pattern[]) {
    int len = strlen(pattern);
    suffix[len-1] = len;
    for(int i = len - 2; i >= 0; --i) {
        int j = i;
        while(j > 0 && pattern[j] == pattern[len-1-(i-j)]) {
            --j;
        }
        suffix[i] = i - j;
    }
}

但其實可以利用已經比好的suffix，只要suffix包含在其中，就可以利用對稱直接算 

inline void getSuffix(int suffix[], char pattern[]) {
    int len = strlen(pattern);
    int g = len-1, f;
    suffix[len-1] = len;
    for(int i = len - 2; i >= 0; --i) {
        if(i > g && suffix[(len-1)-(f-i)] < i - g) {
            suffix[i] = suffix[(len-1)-(f-i)];
        }
        else {
            if(i < g) {
                g = i;
            }
            f = i;
            while(g >= 0 && pattern[g] == pattern[(len-1)-(f-g)]) {
                --g;
            }
            suffix[i] = f - g;
        }
    }
}

Ref

Boyer-Moore 算法 Boyer-Moore algorithm grep之字符串搜索算法Boyer-Moore由浅入深（比KMP快3-5倍）（转） Boyer-Moore-algorithms-good-suffix-shift-examples-15_fig1 Boyer Moore Algorithm | Good Suffix heuristic Boyer-Moore good-suffix heuristics