def naive_search(text: str, pattern: str) -> list:
    """ナイーブ法 - O(nm)"""
    n, m = len(text), len(pattern)
    matches = []
    for i in range(n - m + 1):
        if text[i:i + m] == pattern:
            matches.append(i)
    return matches
 
print(naive_search("ABCABCABD", "ABCABD"))  # [3]

# 最悪ケース: テキスト="AAA...A"(n個), パターン="AA...AB"(m個)
# 各位置で m-1 回一致してから不一致 → O(nm)
text = "A" * 10000
pattern = "A" * 999 + "B"
# ナイーブ法: 9001 * 999 ≈ 9 * 10^6 回の比較
 
# 実用上の改善: Python の `in` 演算子や str.find() は
# Boyer-Moore-Horspool の変種を使っており、ナイーブ法より高速
idx = text.find(pattern)  # 内部で最適化されている

def kmp_search(text: str, pattern: str) -> list:
    """KMP法 - O(n + m)"""
 
    def build_lps(pattern: str) -> list:
        """失敗関数（LPS配列）の構築 - O(m)"""
        m = len(pattern)
        lps = [0] * m
        length = 0
        i = 1
 
        while i < m:
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps
 
    n, m = len(text), len(pattern)
    if m == 0:
        return []
    lps = build_lps(pattern)
    matches = []
    i = j = 0  # i: テキスト, j: パターン
 
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
 
        if j == m:
            matches.append(i - j)
            j = lps[j - 1]
        elif i < n and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]  # パターンをシフト
            else:
                i += 1
 
    return matches
 
text = "AABAACAADAABAABA"
pattern = "AABA"
print(kmp_search(text, pattern))  # [0, 9, 12]

def min_period(s: str) -> int:
    """文字列の最小周期をKMPの失敗関数で求める
    例: "abcabc" の最小周期は 3 ("abc")
    例: "aaaaaa" の最小周期は 1 ("a")
    """
    n = len(s)
    lps = [0] * n
    length = 0
    i = 1
 
    while i < n:
        if s[i] == s[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                i += 1
 
    # 最小周期 = n - lps[n-1]
    period = n - lps[n - 1]
 
    # n が period で割り切れる場合のみ完全な周期
    if n % period == 0:
        return period
    else:
        return n  # 周期構造なし（自身が最小周期）
 
print(min_period("abcabc"))    # 3
print(min_period("aaaaaa"))    # 1
print(min_period("abcab"))     # 5 (完全な周期ではない)
print(min_period("abababab"))  # 2

def count_prefix_occurrences(s: str) -> list:
    """文字列s中で、各接頭辞 s[0..k] が何回出現するか
    返り値: count[k] = s[0..k] の出現回数
    """
    n = len(s)
    lps = [0] * n
    length = 0
    i = 1
 
    while i < n:
        if s[i] == s[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                i += 1
 
    # 各接頭辞の出現回数を数える
    count = [0] * (n + 1)
    for i in range(n):
        count[lps[i]] += 1
 
    # lps の連鎖を辿って累積
    for i in range(n - 1, 0, -1):
        count[lps[i - 1]] += count[i]
 
    # 各接頭辞は少なくとも自分自身として1回出現
    for i in range(n + 1):
        count[i] += 1
 
    return count[1:]  # count[1] ~ count[n]
 
print(count_prefix_occurrences("ababa"))
# "a":3, "ab":2, "aba":2, "abab":1, "ababa":1
# → [3, 2, 2, 1, 1]

def rabin_karp(text: str, pattern: str, prime: int = 101) -> list:
    """Rabin-Karp法 - 平均 O(n+m), 最悪 O(nm)"""
    n, m = len(text), len(pattern)
    if m > n:
        return []
    base = 256
    matches = []
 
    # パターンのハッシュと最初のウィンドウのハッシュ
    p_hash = 0
    t_hash = 0
    h = pow(base, m - 1, prime)  # base^(m-1) mod prime
 
    for i in range(m):
        p_hash = (base * p_hash + ord(pattern[i])) % prime
        t_hash = (base * t_hash + ord(text[i])) % prime
 
    for i in range(n - m + 1):
        if p_hash == t_hash:
            # ハッシュ一致 → 実際に文字列比較（偽陽性を排除）
            if text[i:i + m] == pattern:
                matches.append(i)
 
        if i < n - m:
            # ローリングハッシュ: 先頭を除去、末尾を追加
            t_hash = (base * (t_hash - ord(text[i]) * h) +
                      ord(text[i + m])) % prime
            if t_hash < 0:
                t_hash += prime
 
    return matches
 
print(rabin_karp("AABAACAADAABAABA", "AABA"))  # [0, 9, 12]

class RollingHash:
    """汎用ローリングハッシュ（ダブルハッシュ対応）
    文字列の任意の部分文字列のハッシュを O(1) で計算
    """
 
    def __init__(self, s: str, base1: int = 131, mod1: int = 10**9 + 7,
                 base2: int = 137, mod2: int = 10**9 + 9):
        self.n = len(s)
        self.mod1, self.mod2 = mod1, mod2
 
        # ハッシュの前計算
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.pow1 = [1] * (self.n + 1)
        self.pow2 = [1] * (self.n + 1)
 
        for i in range(self.n):
            self.hash1[i + 1] = (self.hash1[i] * base1 + ord(s[i])) % mod1
            self.hash2[i + 1] = (self.hash2[i] * base2 + ord(s[i])) % mod2
            self.pow1[i + 1] = self.pow1[i] * base1 % mod1
            self.pow2[i + 1] = self.pow2[i] * base2 % mod2
 
    def get_hash(self, l: int, r: int) -> tuple:
        """部分文字列 s[l:r] のハッシュを返す（半開区間）- O(1)"""
        h1 = (self.hash1[r] - self.hash1[l] * self.pow1[r - l]) % self.mod1
        h2 = (self.hash2[r] - self.hash2[l] * self.pow2[r - l]) % self.mod2
        return (h1, h2)
 
    def lcp(self, i: int, j: int) -> int:
        """位置 i と位置 j から始まる最長共通接頭辞の長さ - O(log n)"""
        lo, hi = 0, min(self.n - i, self.n - j)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if self.get_hash(i, i + mid) == self.get_hash(j, j + mid):
                lo = mid
            else:
                hi = mid - 1
        return lo
 
# 使用例
rh = RollingHash("abcabc")
print(rh.get_hash(0, 3) == rh.get_hash(3, 6))  # True ("abc" == "abc")
print(rh.get_hash(0, 3) == rh.get_hash(1, 4))  # False ("abc" != "bca")
print(rh.lcp(0, 3))  # 3 ("abc" と "abc" の共通接頭辞)
 
# 応用: 回文判定
def is_palindrome_hash(s: str, l: int, r: int) -> bool:
    """s[l:r] が回文かどうかをハッシュで判定"""
    rh_forward = RollingHash(s)
    rh_reverse = RollingHash(s[::-1])
    n = len(s)
    h_forward = rh_forward.get_hash(l, r)
    h_reverse = rh_reverse.get_hash(n - r, n - l)
    return h_forward == h_reverse

def count_unique_substrings(s: str) -> int:
    """文字列のユニーク部分文字列の数をローリングハッシュで計算
    O(n^2) で全部分文字列のハッシュを集合に追加
    """
    rh = RollingHash(s)
    unique = set()
    n = len(s)
 
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            h = rh.get_hash(i, i + length)
            unique.add(h)
 
    return len(unique)
 
print(count_unique_substrings("abc"))   # 6: a,b,c,ab,bc,abc
print(count_unique_substrings("aaa"))   # 3: a,aa,aaa

def z_function(s: str) -> list:
    """Z配列の計算 - O(n)"""
    n = len(s)
    z = [0] * n
    z[0] = n
    l, r = 0, 0  # Z-box [l, r)
 
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
 
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
 
        if i + z[i] > r:
            l, r = i, i + z[i]
 
    return z
 
def z_search(text: str, pattern: str) -> list:
    """Z-algorithm によるパターン検索 - O(n+m)"""
    combined = pattern + "$" + text
    z = z_function(combined)
    m = len(pattern)
 
    matches = []
    for i in range(m + 1, len(combined)):
        if z[i] == m:
            matches.append(i - m - 1)
 
    return matches
 
print(z_search("AABAACAADAABAABA", "AABA"))  # [0, 9, 12]

def z_min_period(s: str) -> int:
    """Z配列を使って最小周期を求める"""
    n = len(s)
    z = z_function(s)
 
    for i in range(1, n):
        if i + z[i] == n and n % i == 0:
            return i
    return n
 
print(z_min_period("abcabc"))    # 3
print(z_min_period("abababab"))  # 2
 
def z_count_distinct_substrings(s: str) -> int:
    """Z配列で異なる部分文字列の数を数える - O(n^2)
    各接尾辞の Z 配列を使って「新しく追加される部分文字列」を数える
    """
    n = len(s)
    count = 0
 
    # 右から1文字ずつ追加していく
    current = ""
    for i in range(n - 1, -1, -1):
        current = s[i] + current
        z = z_function(current)
        # 最大の Z[j] (j >= 1) を求める
        max_z = max(z[1:]) if len(z) > 1 else 0
        # 新しい部分文字列の数 = 現在の長さ - 最大 Z 値
        count += len(current) - max_z
 
    return count
 
print(z_count_distinct_substrings("abc"))   # 6
print(z_count_distinct_substrings("aaa"))   # 3

class TrieNode:
    __slots__ = ['children', 'is_end', 'count', 'word']
 
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.count = 0  # この接頭辞を持つ単語数
        self.word = None  # 終端の場合、元の単語を保持
 
class Trie:
    """Trie（トライ木）"""
 
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word: str) -> None:
        """単語を挿入 - O(m)"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.count += 1
        node.is_end = True
        node.word = word
 
    def search(self, word: str) -> bool:
        """完全一致検索 - O(m)"""
        node = self._find_node(word)
        return node is not None and node.is_end
 
    def starts_with(self, prefix: str) -> bool:
        """接頭辞検索 - O(m)"""
        return self._find_node(prefix) is not None
 
    def count_prefix(self, prefix: str) -> int:
        """接頭辞を持つ単語の数"""
        node = self._find_node(prefix)
        return node.count if node else 0
 
    def _find_node(self, prefix: str) -> TrieNode:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node
 
    def auto_complete(self, prefix: str, limit: int = 10) -> list:
        """オートコンプリート"""
        node = self._find_node(prefix)
        if not node:
            return []
 
        results = []
        def dfs(node, path):
            if len(results) >= limit:
                return
            if node.is_end:
                results.append(prefix + path)
            for char, child in sorted(node.children.items()):
                dfs(child, path + char)
 
        dfs(node, "")
        return results
 
    def delete(self, word: str) -> bool:
        """単語を削除 - O(m)"""
        def _delete(node, word, depth):
            if depth == len(word):
                if not node.is_end:
                    return False
                node.is_end = False
                node.word = None
                return len(node.children) == 0
            char = word[depth]
            if char not in node.children:
                return False
 
            child = node.children[char]
            child.count -= 1
            should_delete = _delete(child, word, depth + 1)
 
            if should_delete:
                del node.children[char]
                return len(node.children) == 0 and not node.is_end
 
            return False
 
        return _delete(self.root, word, 0)
 
    def longest_common_prefix(self) -> str:
        """Trie に格納された全単語の最長共通接頭辞"""
        prefix = []
        node = self.root
        while len(node.children) == 1 and not node.is_end:
            char = next(iter(node.children))
            prefix.append(char)
            node = node.children[char]
        return ''.join(prefix)
 
# 使用例
trie = Trie()
for word in ["app", "apple", "apply", "apt", "bat", "bath"]:
    trie.insert(word)
 
print(trie.search("apple"))       # True
print(trie.search("api"))         # False
print(trie.starts_with("ap"))     # True
print(trie.count_prefix("ap"))    # 4
print(trie.auto_complete("ap"))   # ['app', 'apple', 'apply', 'apt']

class ArrayTrie:
    """配列ベースの Trie（高速版、小文字英字限定）
    競技プログラミング向け
    """
 
    def __init__(self, max_nodes: int = 500001):
        self.ALPHA = 26
        self.children = [[0] * self.ALPHA for _ in range(max_nodes)]
        self.is_end = [False] * max_nodes
        self.node_count = 1  # 0 がルート
 
    def _char_to_idx(self, c: str) -> int:
        return ord(c) - ord('a')
 
    def insert(self, word: str) -> None:
        node = 0
        for c in word:
            idx = self._char_to_idx(c)
            if self.children[node][idx] == 0:
                self.children[node][idx] = self.node_count
                self.node_count += 1
            node = self.children[node][idx]
        self.is_end[node] = True
 
    def search(self, word: str) -> bool:
        node = 0
        for c in word:
            idx = self._char_to_idx(c)
            if self.children[node][idx] == 0:
                return False
            node = self.children[node][idx]
        return self.is_end[node]

from collections import deque, defaultdict
 
class AhoCorasick:
    """Aho-Corasick法 - 複数パターン同時検索"""
 
    def __init__(self):
        self.goto = [{}]         # goto関数
        self.fail = [0]          # 失敗関数
        self.output = [[]]       # 出力関数
        self.state_count = 1
 
    def _add_state(self):
        self.goto.append({})
        self.fail.append(0)
        self.output.append([])
        state = self.state_count
        self.state_count += 1
        return state
 
    def add_pattern(self, pattern: str, pattern_id=None):
        """パターンを追加"""
        if pattern_id is None:
            pattern_id = pattern
 
        state = 0
        for char in pattern:
            if char not in self.goto[state]:
                self.goto[state][char] = self._add_state()
            state = self.goto[state][char]
        self.output[state].append(pattern_id)
 
    def build(self):
        """失敗関数を構築 - O(パターン文字数の合計)"""
        queue = deque()
 
        # 深さ1の状態の失敗関数を設定
        for char, state in self.goto[0].items():
            self.fail[state] = 0
            queue.append(state)
 
        # BFS で構築
        while queue:
            r = queue.popleft()
            for char, s in self.goto[r].items():
                queue.append(s)
 
                state = self.fail[r]
                while state != 0 and char not in self.goto[state]:
                    state = self.fail[state]
 
                self.fail[s] = self.goto[state].get(char, 0)
                if self.fail[s] == s:
                    self.fail[s] = 0
 
                self.output[s] = self.output[s] + self.output[self.fail[s]]
 
    def search(self, text: str) -> list:
        """テキスト中の全パターンを検索 - O(n + m + z)"""
        state = 0
        results = []
 
        for i, char in enumerate(text):
            while state != 0 and char not in self.goto[state]:
                state = self.fail[state]
 
            state = self.goto[state].get(char, 0)
 
            for pattern in self.output[state]:
                if isinstance(pattern, str):
                    results.append((i - len(pattern) + 1, pattern))
                else:
                    results.append((i, pattern))
 
        return results
 
# 使用例
ac = AhoCorasick()
patterns = ["he", "she", "his", "hers"]
for p in patterns:
    ac.add_pattern(p)
ac.build()
 
results = ac.search("ahishers")
print(results)
# [(1, 'his'), (3, 'she'), (4, 'he'), (4, 'hers')]

def censor_text(text: str, forbidden_words: list) -> str:
    """テキストから禁止語を '*' で置換する
    Aho-Corasick で一括検出して効率的に処理
    """
    ac = AhoCorasick()
    for word in forbidden_words:
        ac.add_pattern(word.lower())
    ac.build()
 
    text_lower = text.lower()
    matches = ac.search(text_lower)
 
    # 置換する範囲を計算
    censored = list(text)
    for pos, pattern in matches:
        for i in range(pos, pos + len(pattern)):
            censored[i] = '*'
 
    return ''.join(censored)
 
text = "This is a bad example with some ugly words"
forbidden = ["bad", "ugly"]
print(censor_text(text, forbidden))
# "This is a *** example with some **** words"

def build_suffix_array(s: str) -> list:
    """Suffix Array の構築 - O(n log^2 n)"""
    n = len(s)
    # (ランク, 次ランク, インデックス) でソート
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
 
    k = 1
    while k < n:
        def compare(i, j):
            if rank[i] != rank[j]:
                return -1 if rank[i] < rank[j] else 1
            ri = rank[i + k] if i + k < n else -1
            rj = rank[j + k] if j + k < n else -1
            return -1 if ri < rj else (0 if ri == rj else 1)
 
        from functools import cmp_to_key
        sa.sort(key=cmp_to_key(compare))
 
        # 新しいランクを計算
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i-1]]
            if compare(sa[i-1], sa[i]) < 0:
                tmp[sa[i]] += 1
 
        rank = tmp[:]
        if rank[sa[n-1]] == n - 1:
            break
        k *= 1 if k == 0 else k  # k を2倍に
        k *= 2
 
    return sa
 
def build_suffix_array_simple(s: str) -> list:
    """Suffix Array の構築（簡易版）- O(n log n * m)
    Pythonのソートを利用した簡潔な実装
    """
    n = len(s)
    return sorted(range(n), key=lambda i: s[i:])
 
# LCP Array（Kasai's Algorithm）
def build_lcp_array(s: str, sa: list) -> list:
    """LCP Array の構築（Kasai's Algorithm）- O(n)
    lcp[i] = sa[i] と sa[i+1] の最長共通接頭辞の長さ
    """
    n = len(s)
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
 
    lcp = [0] * (n - 1)
    h = 0
 
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i] - 1] = h
            if h > 0:
                h -= 1
        else:
            h = 0
 
    return lcp
 
# 使用例
s = "banana"
sa = build_suffix_array_simple(s)
print(f"SA: {sa}")  # [5, 3, 1, 0, 4, 2]
 
lcp = build_lcp_array(s, sa)
print(f"LCP: {lcp}")  # [1, 3, 0, 0, 2]
 
# 接尾辞の表示
for i, idx in enumerate(sa):
    prefix = f"lcp={lcp[i]}" if i < len(lcp) else ""
    print(f"  sa[{i}]={idx}: {s[idx:]:10s}  {prefix}")

def search_with_suffix_array(text: str, pattern: str) -> list:
    """Suffix Array を使ったパターン検索 - O(m log n)"""
    sa = build_suffix_array_simple(text)
    n = len(text)
    m = len(pattern)
 
    # 二分探索で下界を見つける
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if text[sa[mid]:sa[mid] + m] < pattern:
            lo = mid + 1
        else:
            hi = mid
    left = lo
 
    # 二分探索で上界を見つける
    hi = n
    while lo < hi:
        mid = (lo + hi) // 2
        if text[sa[mid]:sa[mid] + m] <= pattern:
            lo = mid + 1
        else:
            hi = mid
    right = lo
 
    return sorted(sa[left:right])
 
text = "banana"
print(search_with_suffix_array(text, "ana"))  # [1, 3]
print(search_with_suffix_array(text, "ban"))  # [0]
 
def longest_repeated_substring(s: str) -> str:
    """最長反復部分文字列（文字列中に2回以上出現する最長部分文字列）
    LCP Array の最大値を使う
    """
    if len(s) <= 1:
        return ""
 
    sa = build_suffix_array_simple(s)
    lcp = build_lcp_array(s, sa)
 
    if not lcp:
        return ""
 
    max_lcp = max(lcp)
    max_idx = lcp.index(max_lcp)
 
    return s[sa[max_idx]:sa[max_idx] + max_lcp]
 
print(longest_repeated_substring("banana"))    # "ana"
print(longest_repeated_substring("abcabc"))    # "abc"
print(longest_repeated_substring("aabaaab"))   # "aab"
 
def count_distinct_substrings_sa(s: str) -> int:
    """Suffix Array + LCP で異なる部分文字列の数を計算 - O(n log n)
    全部分文字列数 n*(n+1)/2 から重複（LCPの総和）を引く
    """
    n = len(s)
    sa = build_suffix_array_simple(s)
    lcp = build_lcp_array(s, sa)
 
    total = n * (n + 1) // 2
    duplicates = sum(lcp)
    return total - duplicates
 
print(count_distinct_substrings_sa("abc"))    # 6
print(count_distinct_substrings_sa("aaa"))    # 3
print(count_distinct_substrings_sa("banana")) # 15

def manacher(s: str) -> list:
    """Manacher法 - 各位置を中心とする最長回文の半径を計算
    O(n)
 
    入力文字列を加工して偶数長回文も統一的に扱う:
    "abba" → "#a#b#b#a#"
    """
    # 文字間にダミー文字を挿入
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n  # p[i] = 位置 i を中心とする回文の半径
 
    c = r = 0  # 最も右に到達した回文の中心と右端
 
    for i in range(n):
        # ミラーの位置
        mirror = 2 * c - i
 
        if i < r:
            p[i] = min(r - i, p[mirror])
 
        # 拡張を試みる
        while (i + p[i] + 1 < n and i - p[i] - 1 >= 0
               and t[i + p[i] + 1] == t[i - p[i] - 1]):
            p[i] += 1
 
        # 右端を超えたら更新
        if i + p[i] > r:
            c, r = i, i + p[i]
 
    return p
 
def longest_palindrome_substring(s: str) -> str:
    """最長回文部分文字列 - O(n)"""
    if not s:
        return ""
 
    t = '#' + '#'.join(s) + '#'
    p = manacher(s)
 
    # 加工後文字列での最長回文を見つける
    # p 配列から直接計算
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p2 = [0] * n
    c = r = 0
 
    for i in range(n):
        mirror = 2 * c - i
        if i < r:
            p2[i] = min(r - i, p2[mirror])
        while (i + p2[i] + 1 < n and i - p2[i] - 1 >= 0
               and t[i + p2[i] + 1] == t[i - p2[i] - 1]):
            p2[i] += 1
        if i + p2[i] > r:
            c, r = i, i + p2[i]
 
    # 最大半径の位置
    max_len = max(p2)
    center = p2.index(max_len)
 
    # 元の文字列での開始位置と長さ
    start = (center - max_len) // 2
    return s[start:start + max_len]
 
print(longest_palindrome_substring("babad"))     # "bab" or "aba"
print(longest_palindrome_substring("cbbd"))      # "bb"
print(longest_palindrome_substring("abacaba"))   # "abacaba"
 
def count_palindromic_substrings(s: str) -> int:
    """回文部分文字列の総数 - O(n)"""
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    c = r = 0
 
    for i in range(n):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        while (i + p[i] + 1 < n and i - p[i] - 1 >= 0
               and t[i + p[i] + 1] == t[i - p[i] - 1]):
            p[i] += 1
        if i + p[i] > r:
            c, r = i, i + p[i]
 
    # # 位置の回文は偶数長回文に対応
    # 元文字位置の回文は奇数長回文に対応
    count = 0
    for i in range(n):
        # p[i] の中に含まれる回文の数
        if t[i] == '#':
            count += p[i] // 2  # 偶数長
        else:
            count += (p[i] + 1) // 2  # 奇数長
 
    return count
 
print(count_palindromic_substrings("abc"))   # 3 (a, b, c)
print(count_palindromic_substrings("aaa"))   # 6 (a,a,a,aa,aa,aaa)

def boyer_moore_horspool(text: str, pattern: str) -> list:
    """Boyer-Moore-Horspool法（簡易版）
    平均 O(n/m), 最悪 O(nm)
    """
    n, m = len(text), len(pattern)
    if m > n:
        return []
 
    # Bad Character テーブルの構築
    bad_char = {}
    for i in range(m - 1):
        bad_char[pattern[i]] = m - 1 - i
 
    matches = []
    i = 0
 
    while i <= n - m:
        j = m - 1
        while j >= 0 and text[i + j] == pattern[j]:
            j -= 1
 
        if j < 0:
            matches.append(i)
            i += 1
        else:
            # Bad Character Rule でシフト
            skip = bad_char.get(text[i + m - 1], m)
            i += max(1, skip)
 
    return matches
 
print(boyer_moore_horspool("ABCABCABD", "ABCABD"))  # [3]
 
# Boyer-Moore が実用上最速な理由:
# - パターンを右から左に比較 → 不一致が早期に検出される
# - Bad Character Rule: 不一致文字がパターンに存在しなければ m 文字シフト
# - Good Suffix Rule: パターン内部の一致部分を活用してシフト
# - 英語テキストなどでは平均的に O(n/m) の比較回数

def analyze_logs(log_lines: list, error_patterns: list) -> dict:
    """ログファイルからエラーパターンを一括検出"""
    ac = AhoCorasick()
    for i, pattern in enumerate(error_patterns):
        ac.add_pattern(pattern.lower(), i)
    ac.build()
 
    results = {p: [] for p in error_patterns}
 
    for line_num, line in enumerate(log_lines, 1):
        matches = ac.search(line.lower())
        for _, pattern_id in matches:
            results[error_patterns[pattern_id]].append(line_num)
 
    return results
 
logs = [
    "2024-01-15 INFO Server started",
    "2024-01-15 ERROR Connection timeout",
    "2024-01-15 WARN Memory usage high",
    "2024-01-15 ERROR Disk full",
    "2024-01-15 ERROR Connection refused",
]
patterns = ["error", "timeout", "memory"]
result = analyze_logs(logs, patterns)
print(result)
# {'error': [2, 4, 5], 'timeout': [2], 'memory': [3]}

def find_motifs(dna: str, motifs: list) -> dict:
    """DNA配列中のモチーフ（特定パターン）を一括検索"""
    ac = AhoCorasick()
    for motif in motifs:
        ac.add_pattern(motif)
    ac.build()
 
    results = {m: [] for m in motifs}
    matches = ac.search(dna)
 
    for pos, motif in matches:
        results[motif].append(pos)
 
    return results
 
dna = "ATCGATCGATCGATCG"
motifs = ["ATC", "GAT", "ATCG"]
print(find_motifs(dna, motifs))
# {'ATC': [0, 4, 8, 12], 'GAT': [3, 7, 11], 'ATCG': [0, 4, 8, 12]}

def spell_checker(dictionary: list, word: str, max_distance: int = 1) -> list:
    """Trieを使ったスペルチェッカー（編集距離ベース）"""
    trie = Trie()
    for w in dictionary:
        trie.insert(w)
 
    suggestions = []
 
    def search_recursive(node, char_idx, word, current_row, results):
        columns = len(word) + 1
        if node.is_end and current_row[-1] <= max_distance:
            results.append((node.word, current_row[-1]))
 
        for char, child_node in node.children.items():
            new_row = [current_row[0] + 1]
            for col in range(1, columns):
                insert_cost = new_row[col - 1] + 1
                delete_cost = current_row[col] + 1
                replace_cost = current_row[col - 1]
                if word[col - 1] != char:
                    replace_cost += 1
                new_row.append(min(insert_cost, delete_cost, replace_cost))
 
            if min(new_row) <= max_distance:
                search_recursive(child_node, char_idx, word, new_row, results)
 
    current_row = list(range(len(word) + 1))
    for char, node in trie.root.children.items():
        new_row = [1]
        for col in range(1, len(word) + 1):
            insert_cost = new_row[col - 1] + 1
            delete_cost = current_row[col] + 1
            replace_cost = current_row[col - 1]
            if word[col - 1] != char:
                replace_cost += 1
            new_row.append(min(insert_cost, delete_cost, replace_cost))
 
        if min(new_row) <= max_distance:
            search_recursive(node, 0, word, new_row, suggestions)
 
    return sorted(suggestions, key=lambda x: x[1])
 
dictionary = ["apple", "apply", "app", "ape", "maple", "application"]
print(spell_checker(dictionary, "aple"))
# [('ape', 1), ('apple', 1)]

# BAD: 大きなテキストでナイーブ法を繰り返す
text = "A" * 1000000
pattern = "A" * 999
# O(n*m) = O(10^12) → タイムアウト
 
# GOOD: KMP or Z-algorithm を使う
matches = kmp_search(text, pattern)  # O(n+m) = O(10^6)

# BAD: k 個のパターンを個別に KMP で検索 → O(k * (n+m))
patterns = ["pattern1", "pattern2", "patternK"]
for p in patterns:
    kmp_search(text, p)  # k回繰り返し
 
# GOOD: Aho-Corasick で一括検索 → O(n + Σm + z)
ac = AhoCorasick()
for p in patterns:
    ac.add_pattern(p)
ac.build()
results = ac.search(text)  # 1回の走査

# BAD: 単一ハッシュで偽陽性を検証しない
def bad_rabin_karp(text, pattern):
    # ハッシュが一致したら即マッチと判定
    if hash_match:
        matches.append(i)  # 偽陽性の可能性!
 
# GOOD: ダブルハッシュまたはハッシュ一致時に文字列比較
def good_rabin_karp(text, pattern):
    if hash_match:
        if text[i:i+m] == pattern:  # 検証
            matches.append(i)

# BAD: 大量の長い文字列を辞書型 Trie に格納
# 各ノードが dict を持つ → メモリ消費が大きい
 
# GOOD:
# 1. 配列ベースの Trie（文字種が限定的な場合）
# 2. ダブル配列 Trie（メモリ効率が良い）
# 3. Patricia Trie / Radix Tree（共通接頭辞を圧縮）

# 演習1: 基本実装のテンプレート
class Exercise1:
    """基本的な実装パターンの演習"""
 
    def __init__(self):
        self.data = []
 
    def validate_input(self, value):
        """入力値の検証"""
        if value is None:
            raise ValueError("入力値がNoneです")
        return True
 
    def process(self, value):
        """データ処理のメインロジック"""
        self.validate_input(value)
        self.data.append(value)
        return self.data
 
    def get_results(self):
        """処理結果の取得"""
        return {
            'count': len(self.data),
            'data': self.data
        }
 
# テスト
def test_exercise1():
    ex = Exercise1()
    assert ex.process(1) == [1]
    assert ex.process(2) == [1, 2]
    assert ex.get_results()['count'] == 2
 
    try:
        ex.process(None)
        assert False, "例外が発生するべき"
    except ValueError:
        pass
 
    print("全テスト合格!")
 
test_exercise1()

# 演習2: 応用パターン
from typing import List, Dict, Optional
from datetime import datetime
 
class AdvancedExercise:
    """応用パターンの演習"""
 
    def __init__(self, max_size: int = 100):
        self._items: List[Dict] = []
        self._max_size = max_size
        self._created_at = datetime.now()
 
    def add(self, key: str, value: any) -> bool:
        """アイテムの追加（サイズ制限付き）"""
        if len(self._items) >= self._max_size:
            return False
        self._items.append({
            'key': key,
            'value': value,
            'timestamp': datetime.now().isoformat()
        })
        return True
 
    def find(self, key: str) -> Optional[Dict]:
        """キーによる検索"""
        for item in reversed(self._items):
            if item['key'] == key:
                return item
        return None
 
    def remove(self, key: str) -> bool:
        """キーによる削除"""
        for i, item in enumerate(self._items):
            if item['key'] == key:
                self._items.pop(i)
                return True
        return False
 
    def stats(self) -> Dict:
        """統計情報"""
        return {
            'total_items': len(self._items),
            'max_size': self._max_size,
            'usage_percent': len(self._items) / self._max_size * 100,
            'uptime': str(datetime.now() - self._created_at)
        }
 
# テスト
def test_advanced():
    ex = AdvancedExercise(max_size=3)
    assert ex.add("a", 1) == True
    assert ex.add("b", 2) == True
    assert ex.add("c", 3) == True
    assert ex.add("d", 4) == False  # サイズ制限
    assert ex.find("b")['value'] == 2
    assert ex.remove("b") == True
    assert ex.find("b") is None
    stats = ex.stats()
    assert stats['total_items'] == 2
    print("応用テスト全合格!")
 
test_advanced()

# 演習3: パフォーマンス最適化
import time
from functools import lru_cache
 
# 最適化前（O(n^2)）
def slow_search(data: list, target: int) -> int:
    """非効率な検索"""
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] + data[j] == target:
                return (i, j)
    return (-1, -1)
 
# 最適化後（O(n)）
def fast_search(data: list, target: int) -> tuple:
    """ハッシュマップを使った効率的な検索"""
    seen = {}
    for i, num in enumerate(data):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return (-1, -1)
 
# ベンチマーク
def benchmark():
    import random
    data = list(range(5000))
    random.shuffle(data)
    target = data[100] + data[4000]
 
    start = time.time()
    result1 = slow_search(data, target)
    slow_time = time.time() - start
 
    start = time.time()
    result2 = fast_search(data, target)
    fast_time = time.time() - start
 
    print(f"非効率版: {slow_time:.4f}秒")
    print(f"効率版:   {fast_time:.6f}秒")
    print(f"高速化率: {slow_time/fast_time:.0f}倍")
 
benchmark()

# デバッグ用ユーティリティ
import logging
import traceback
from functools import wraps
 
# ロガーの設定
logging.basicConfig(
    level=logging.DEBUG,
    format='%(asctime)s [%(levelname)s] %(name)s: %(message)s'
)
logger = logging.getLogger(__name__)
 
def debug_decorator(func):
    """関数の入出力をログ出力するデコレータ"""
    @wraps(func)
    def wrapper(*args, **kwargs):
        logger.debug(f"呼び出し: {func.__name__}(args={args}, kwargs={kwargs})")
        try:
            result = func(*args, **kwargs)
            logger.debug(f"戻り値: {func.__name__} -> {result}")
            return result
        except Exception as e:
            logger.error(f"例外発生: {func.__name__}: {e}")
            logger.error(traceback.format_exc())
            raise
    return wrapper
 
@debug_decorator
def process_data(items):
    """データ処理（デバッグ対象）"""
    if not items:
        raise ValueError("空のデータ")
    return [item * 2 for item in items]