KMPアルゴリズムのnext配列最適化

KMP（Knuth-Morris-Pratt）アルゴリズムでは、パターン文字列の部分一致情報を格納したnext配列を用いて、主文字列との照合時に不要な比較をスキップする。しかし、標準的なnext配列には冗長な比較が含まれる場合があるため、これをさらに最適化することが可能である。

最適化が必要なケース1

例えば、パターン文字列の先頭文字と現在の失敗位置の文字が同じ場合、単純にnext[j]に従ってシフトすると、再度同じ文字同士の比較が発生し、無駄になる。このような状況では、さらに前の共通接頭辞・接尾辞の情報を参照すべきである。

最適化が必要なケース2

パターン文字列が"ABCABC"で、マッチング中に最後の'C'で失敗したとする。next[5] = 2の場合、次はj = 2から再開するが、この位置の文字も'C'であり、再び同じ失敗が起こる。これは、現在の共通部分（"AB"）が失敗文字と同じ文字で終わっているためである。

このような場合、単にnext[j] = kとするのではなく、next[j] = next[k]とすることで、より短い有効な共通部分へとジャンプできる。

最適化されたnext配列の構築ロジック

next配列を構築する際に、次の条件を追加する：

• T.charAt(k) == T.charAt(j) の場合、next[j] = next[k] と設定
• そうでなければ、通常通り next[j] = k

これにより、冗長な比較を回避し、実行効率が向上する。

Javaによる実装例

public class OptimizedKMP {
    public static int find(String text, String pattern) {
        if (pattern.isEmpty()) return 0;
        int[] next = buildOptimizedNext(pattern);
        int i = 0, j = 0;
        while (i < text.length() && j < pattern.length()) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        return j == pattern.length() ? i - j : -1;
    }

    private static int[] buildOptimizedNext(String pattern) {
        int n = pattern.length();
        int[] next = new int[n];
        next[0] = -1;
        int j = 0, k = -1;
        while (j < n - 1) {
            if (k == -1 || pattern.charAt(k) == pattern.charAt(j)) {
                k++;
                j++;
                if (pattern.charAt(k) == pattern.charAt(j)) {
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }
}

C++による実装例

#include <string>
#include <vector>

std::vector<int> buildOptimizedNext(const std::string& pattern) {
    int n = pattern.size();
    std::vector<int> next(n);
    next[0] = -1;
    int j = 0, k = -1;
    while (j < n - 1) {
        if (k == -1 || pattern[k] == pattern[j]) {
            ++k;
            ++j;
            if (pattern[k] == pattern[j]) {
                next[j] = next[k];
            } else {
                next[j] = k;
            }
        } else {
            k = next[k];
        }
    }
    return next;
}

int kmpSearch(const std::string& text, const std::string& pattern) {
    if (pattern.empty()) return 0;
    auto next = buildOptimizedNext(pattern);
    int i = 0, j = 0;
    while (i < text.size() && j < pattern.size()) {
        if (j == -1 || text[i] == pattern[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    return (j == pattern.size()) ? i - j : -1;
}