lessons/互动程序/04-KMP与Manacher/00-不从头再看的字符串.py

#!/usr/bin/env python3
"""课前零食：追踪 KMP 的 border 与 Manacher 的镜像半径。"""

from __future__ import annotations


def ask(prompt: str, default: str) -> str:
    try:
        return input(prompt).strip() or default
    except EOFError:
        return default


def prefix_function(pattern: str) -> list[int]:
    pi = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j and pattern[i] != pattern[j]:
            print(f"i={i}，{pattern[i]} != {pattern[j]}：j 从 {j} 跳到 pi[{j - 1}]={pi[j - 1]}")
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
        print(f"pi[{i}]={j}（{pattern[:i + 1]!r} 的最长 border）")
    return pi


def naive_count(text: str, pattern: str) -> int:
    comparisons = 0
    for start in range(len(text) - len(pattern) + 1):
        for j, char in enumerate(pattern):
            comparisons += 1
            if text[start + j] != char:
                break
    return comparisons


def kmp_lab() -> None:
    pattern = ask("模式串（回车为 ABABAC）： ", "ABABAC")
    text = ask("文本串（回车为 ABABABACABA）： ", "ABABABACABA")
    if not pattern:
        print("空模式串没有可演示的失配；请下次输入至少一个字符。")
        return
    print("\n--- 构建前缀函数 ---")
    pi = prefix_function(pattern)
    print("pi =", pi)
    print("\n--- 扫描文本 ---")
    j = 0
    matches: list[int] = []
    for i, char in enumerate(text):
        while j and char != pattern[j]:
            print(f"文本[{i}]={char} 失配：j {j} -> {pi[j - 1]}")
            j = pi[j - 1]
        if char == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            print(f"在位置 {matches[-1]} 匹配成功；保留 border，j -> {pi[j - 1]}")
            j = pi[j - 1]
    print("匹配位置：", matches or "没有")
    print(f"朴素法会做 {naive_count(text, pattern)} 次字符比较（KMP 只维护一条 border 链）。")


def manacher_lab() -> None:
    text = ask("字符串（回车为 abacaba）： ", "abacaba")
    if not text:
        print("空串的回文半径没有戏份。")
        return
    radius = [0] * len(text)
    left, right = 0, -1
    print("\n--- 奇长度回文半径（含中心） ---")
    for center in range(len(text)):
        radius[center] = 1 if center > right else min(radius[left + right - center], right - center + 1)
        source = "从 1 开始" if center > right else f"借镜像 {left + right - center}"
        while center - radius[center] >= 0 and center + radius[center] < len(text) and text[center - radius[center]] == text[center + radius[center]]:
            radius[center] += 1
        if center + radius[center] - 1 > right:
            left = center - radius[center] + 1
            right = center + radius[center] - 1
        covered = text[center - radius[center] + 1:center + radius[center]]
        print(f"中心 {center}={text[center]!r}：{source}，半径 {radius[center]}，覆盖 {covered!r}，当前 [L,R]=[{left},{right}]")
    print("半径数组：", radius)


def main() -> None:
    choice = ask("字符串实验室：k=KMP，m=Manacher（回车为 k）： ", "k").lower()
    if choice == "m":
        manacher_lab()
    else:
        kmp_lab()


if __name__ == "__main__":
    main()