LeetCode 28: 文字列の中で最初に一致するインデックスを検索する

問題リンク: 28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

KMPアルゴリズムを使用して、部分文字列を効率的に検索します。ここでは、失敗時のバックトラックテーブル（Next/LPS配列）を構築し、メイン文字列とパターンを比較します。

Python実装例

class Solution:
    def build_lps(self, pattern: str):
        """部分文字列のLongest Prefix Suffixテーブルを作成"""
        lps = [0] * len(pattern)
        prev_len = 0
        idx = 1
        
        while idx < len(pattern):
            if pattern[idx] == pattern[prev_len]:
                prev_len += 1
                lps[idx] = prev_len
                idx += 1
            else:
                if prev_len != 0:
                    prev_len = lps[prev_len - 1]
                else:
                    lps[idx] = 0
                    idx += 1
        return lps

    def strStr(self, text: str, pattern: str) -> int:
        if not pattern:
            return 0
        if not text:
            return -1
            
        lps = self.build_lps(pattern)
        i = 0  # textのインデックス
        j = 0  # patternのインデックス
        
        while i < len(text):
            if text[i] == pattern[j]:
                i += 1
                j += 1
                
            if j == len(pattern):
                return i - j
            elif i < len(text) and text[i] != pattern[j]:
                if j != 0:
                    j = lps[j - 1]
                else:
                    i += 1
        return -1

Java実装例

class Solution {
    public int strStr(String mainStr, String subStr) {
        if (subStr.length() == 0) return 0;
        
        int[] fail = new int[subStr.length()];
        int j = 0;
        
        // 失敗テーブルの構築
        for (int i = 1; i < subStr.length(); i++) {
            while (j > 0 && subStr.charAt(i) != subStr.charAt(j)) {
                j = fail[j - 1];
            }
            if (subStr.charAt(i) == subStr.charAt(j)) {
                j++;
            }
            fail[i] = j;
        }
        
        j = 0;
        // メイン文字列の走査
        for (int i = 0; i < mainStr.length(); i++) {
            while (j > 0 && mainStr.charAt(i) != subStr.charAt(j)) {
                j = fail[j - 1];
            }
            if (mainStr.charAt(i) == subStr.charAt(j)) {
                j++;
            }
            if (j == subStr.length()) {
                return i - subStr.length() + 1;
            }
        }
        return -1;
    }
}

KMPアルゴリズムの核心は、パターン自身の比較においてすでに得られた情報を再利用し、無駄な比較を省くことです。テーブル構築と検索のロジックが非常に似ているのは、両方とも「パターンの自己比較」という本質的な操作に基づいているためです。

LeetCode 459: 繰り返される部分文字列のパターン判定

問題リンク: 459. 重复的子字符串 - 力扣（LeetCode）

この問題もKMPのLPS配列を応用して解決できます。文字列が「ある部分文字列の繰り返し」で構成されているかどうかを判定するには、LPSの最後の値を利用します。

Python実装例

class Solution:
    def build_prefix_table(self, target: str):
        """KMP用のプレフィックステーブル作成"""
        table = [0] * len(target)
        j = 0
        i = 1
        
        while i < len(target):
            if target[i] == target[j]:
                j += 1
                table[i] = j
                i += 1
            else:
                if j > 0:
                    j = table[j - 1]
                else:
                    table[i] = 0
                    i += 1
        return table

    def repeatedSubstringPattern(self, s: str) -> bool:
        if len(s) == 0:
            return False
            
        prefix_tbl = self.build_prefix_table(s)
        last_val = prefix_tbl[-1]
        # 最後のLPS値が0でなく、文字列長が「全体長 - 最後のLPS値」で割り切れれば真
        return last_val > 0 and len(s) % (len(s) - last_val) == 0

判定のポイントは、文字列の末尾で一致した長さ（LPSの最後の値）が存在し、かつ文字列全体の長さが「(全体長 - その一致長)」で割り切れる場合、元の文字列はその「補完部分」を繰り返して構成されていると言えます。これはKMPの性質を巧みに利用した解法です。