字符串算法（String Algorithms）完全详解 - 从暴力到KMP¶

# Python中的字符串
s = "Hello"

# 内存结构（简化）
# 每个字符占1-4字节（取决于编码）
# ASCII: 1字节/字符
# Unicode: 2-4字节/字符

s = "Hello"
# 内存:
# [H][e][l][l][o]
#  ↑  ↑  ↑  ↑  ↑
#  0  1  2  3  4  (索引)

# 字符串长度
len(s)  # 5

# 访问字符
s[0]    # 'H'
s[-1]   # 'o' (最后一个)

# 切片
s[1:4]  # 'ell'
s[::2]  # 'Hlo' (每隔一个)

def brute_force_match(text, pattern):
    """
    暴力字符串匹配
    时间：O(mn), m=len(text), n=len(pattern)
    空间：O(1)
    """
    m, n = len(text), len(pattern)

    if n == 0:
        return []
    if m < n:
        return []

    positions = []

    print(f"文本串: {text}")
    print(f"模式串: {pattern}")
    print(f"\n匹配过程:")

    # 遍历text的每个位置
    for i in range(m - n + 1):
        print(f"\n位置{i}: ", end="")

        # 检查从i开始是否匹配
        match = True
        for j in range(n):
            print(f"{text[i+j]}", end="")
            if text[i+j] != pattern[j]:
                print(" ✗", end="")
                match = False
                break

        if match:
            print(" ✓ 匹配！")
            positions.append(i)
        else:
            print()

    print(f"\n匹配位置: {positions}")
    return positions

# 测试
print("=" * 60)
print("暴力匹配算法")
print("=" * 60)

text = "ABABABC"
pattern = "ABA"
positions = brute_force_match(text, pattern)

# 输出：
# ============================================================
# 暴力匹配算法
# ============================================================
# 文本串: ABABABC
# 模式串: ABA
#
# 匹配过程:
#
# 位置0: ABA ✓ 匹配！
#
# 位置1: BAB ✗
#
# 位置2: ABA ✓ 匹配！
#
# 位置3: BAB ✗
#
# 位置4: ABC ✗
#
# 匹配位置: [0, 2]

def compute_next(pattern):
    """
    计算KMP的next数组
    时间：O(m), m=len(pattern)
    """
    m = len(pattern)
    next_arr = [0] * m

    print("计算next数组:")
    print(f"模式串: {pattern}")
    print(f"索引:   {' '.join(str(i).rjust(3) for i in range(m))}")
    print(f"字符:   {'  '.join(pattern)}")
    print()

    # j表示前缀长度
    j = 0

    for i in range(1, m):
        # 当不匹配时，回退到前一个位置
        while j > 0 and pattern[i] != pattern[j]:
            print(f"  next[{i}]: pattern[{i}]({pattern[i]}) != pattern[{j}]({pattern[j]}), j从{j}回退到next[{j-1}]={next_arr[j-1]}")
            j = next_arr[j-1]

        # 当匹配时，前缀长度+1
        if pattern[i] == pattern[j]:
            j += 1
            print(f"  next[{i}]: pattern[{i}]({pattern[i]}) == pattern[{j-1}]({pattern[j-1]}), j={j}")

        next_arr[i] = j
        print(f"  → next[{i}] = {j}\n")

    print(f"next数组: {next_arr}")
    return next_arr

# 测试
print("=" * 60)
print("计算next数组")
print("=" * 60)

pattern = "ABABCABAB"
next_arr = compute_next(pattern)

# 输出：
# ============================================================
# 计算next数组
# ============================================================
# 模式串: ABABCABAB
# 索引:   0  1  2  3  4  5  6  7  8
# 字符:   A  B  A  B  C  A  B  A  B
#
#   next[1]: pattern[1](B) != pattern[0](A), j从0回退到next[-1]=0
#   → next[1] = 0
#
#   next[2]: pattern[2](A) == pattern[0](A), j=1
#   → next[2] = 1
#
#   next[3]: pattern[3](B) == pattern[1](B), j=2
#   → next[3] = 2
#
#   next[4]: pattern[4](C) != pattern[2](A), j从2回退到next[1]=0
#   → next[4] = 0
#
#   next[5]: pattern[5](A) == pattern[0](A), j=1
#   → next[5] = 1
#
#   next[6]: pattern[6](B) == pattern[1](B), j=2
#   → next[6] = 2
#
#   next[7]: pattern[7](A) == pattern[2](A), j=3
#   → next[7] = 3
#
#   next[8]: pattern[8](B) == pattern[3](B), j=4
#   → next[8] = 4
#
# next数组: [0, 0, 1, 2, 0, 1, 2, 3, 4]

def kmp_search(text, pattern):
    """
    KMP字符串匹配
    时间：O(m+n), m=len(text), n=len(pattern)
    空间：O(n) (next数组)
    """
    m, n = len(text), len(pattern)

    if n == 0:
        return []
    if m < n:
        return []

    # 第1步：计算next数组
    next_arr = compute_next(pattern)

    # 第2步：KMP匹配
    print(f"\nKMP匹配过程:")
    print(f"文本串: {text}")
    print(f"模式串: {pattern}\n")

    positions = []
    j = 0  # pattern的索引

    for i in range(m):
        print(f"\n比较T[{i}]({text[i]})和P[{j}]({pattern[j]})", end="")

        # 当不匹配时，根据next数组回退j
        while j > 0 and text[i] != pattern[j]:
            print(f" ✗ 不匹配, j从{j}回退到{next_arr[j-1]}")
            j = next_arr[j-1]
            print(f"  → 比较T[{i}]({text[i]})和P[{j}]({pattern[j]})", end="")

        # 匹配，j前进
        if text[i] == pattern[j]:
            print(" ✓ 匹配")
            j += 1
        else:
            print(" ✗ 不匹配")

        # 完全匹配
        if j == n:
            pos = i - n + 1
            positions.append(pos)
            print(f"  *** 找到匹配，位置{pos} ***")

            # 继续查找下一个匹配
            j = next_arr[j-1]
            print(f"  j重置为{j}，继续查找")

    print(f"\n匹配位置: {positions}")
    return positions

# 测试
print("\n" + "=" * 60)
print("KMP算法")
print("=" * 60)

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
positions = kmp_search(text, pattern)

# 输出：
# ============================================================
# KMP算法
# ============================================================
# 模式串: ABABCABAB
# 索引:   0  1  2  3  4  5  6  7  8
# 字符:   A  B  A  B  C  A  B  A  B
# ...
# (next数组计算过程)
# ...
# KMP匹配过程:
# 文本串: ABABDABACDABABCABAB
# 模式串: ABABCABAB
#
# 比较T[0](A)和P[0](A) ✓ 匹配
# 比较T[1](B)和P[1](B) ✓ 匹配
# 比较T[2](A)和P[2](A) ✓ 匹配
# 比较T[3](B)和P[3](B) ✓ 匹配
# 比较T[4](D)和P[4](C) ✗ 不匹配, j从4回退到0
# 比较T[4](D)和P[0](A) ✗ 不匹配
# ...
# (最终找到匹配)

def rabin_karp_search(text, pattern, base=256, prime=101):
    """
    Rabin-Karp字符串匹配
    时间：O(mn)最坏, 平均O(m+n)
    空间：O(1)
    """
    m, n = len(text), len(pattern)

    if n == 0:
        return []
    if m < n:
        return []

    print(f"文本串: {text}")
    print(f"模式串: {pattern}")
    print(f"基数: {base}, 质数: {prime}\n")

    # 计算模式串的哈希
    pattern_hash = 0
    for char in pattern:
        pattern_hash = (pattern_hash * base + ord(char)) % prime

    print(f"模式串哈希: {pattern_hash}")

    # 计算text第一个窗口的哈希
    text_hash = 0
    for i in range(n):
        text_hash = (text_hash * base + ord(text[i])) % prime

    # base^(n-1) % prime（用于移除最左边的字符）
    h = 1
    for i in range(n-1):
        h = (h * base) % prime

    positions = []

    print(f"\n滚动哈希过程:")

    # 滑动窗口
    for i in range(m - n + 1):
        print(f"\n位置{i}: ", end="")

        # 哈希值相同，验证
        if text_hash == pattern_hash:
            print(f"哈希匹配({text_hash}), 验证: ", end="")

            # 逐字符验证
            match = True
            for j in range(n):
                print(f"{text[i+j]}", end="")
                if text[i+j] != pattern[j]:
                    print(" ✗ 哈希冲突")
                    match = False
                    break

            if match:
                print(" ✓ 完全匹配")
                positions.append(i)
        else:
            print(f"哈希不匹配 ({text_hash} != {pattern_hash})")

        # 计算下一个窗口的哈希
        if i < m - n:
            # 移除最左边的字符，添加新字符
            text_hash = (text_hash - ord(text[i]) * h) % prime
            text_hash = (text_hash * base + ord(text[i + n])) % prime
            text_hash = (text_hash + prime) % prime  # 确保正数

    print(f"\n匹配位置: {positions}")
    return positions

# 测试
print("\n" + "=" * 60)
print("Rabin-Karp算法")
print("=" * 60)

text = "ABABABC"
pattern = "ABA"
positions = rabin_karp_search(text, pattern)

# 输出：
# ============================================================
# Rabin-Karp算法
# ============================================================
# 文本串: ABABABC
# 模式串: ABA
# 基数: 256, 质数: 101
#
# 模式串哈希: 17
#
# 滚动哈希过程:
#
# 位置0: 哈希匹配(17), 验证: ABA ✓ 完全匹配
#
# 位置1: 哈希不匹配 (16 != 17)
#
# 位置2: 哈希匹配(17), 验证: ABA ✓ 完全匹配
#
# 位置3: 哈希不匹配 (16 != 17)
#
# 位置4: 哈希不匹配 (18 != 17)
#
# 匹配位置: [0, 2]

def boyer_moore_search(text, pattern):
    """
    Boyer-Moore字符串匹配（简化版：仅坏字符规则）
    时间：O(mn)最坏, 通常O(m/n)
    空间：O(字符集大小)
    """
    m, n = len(text), len(pattern)

    if n == 0:
        return []
    if m < n:
        return []

    # 预处理：坏字符表
    # bad_char[c] = 字符c在pattern中最右出现的位置
    bad_char = {}

    print("构建坏字符表:")
    for i, char in enumerate(pattern):
        bad_char[char] = i
        print(f"  '{char}': 最右位置={i}")

    print(f"\n坏字符表: {bad_char}\n")

    positions = []
    shift = 0  # pattern相对于text的偏移

    print("匹配过程:")

    while shift <= m - n:
        print(f"\n偏移{shift}: ", end="")

        j = n - 1  # 从pattern最右边开始

        # 从右向左匹配
        while j >= 0 and text[shift + j] == pattern[j]:
            print(f"T[{shift+j}]{text[shift+j]}==P[{j}]{pattern[j]} ", end="")
            j -= 1

        # 完全匹配
        if j < 0:
            print("\n  ✓ 完全匹配")
            positions.append(shift)

            # 继续查找
            if shift + n < m:
                bad_char_text = text[shift + n]
                if bad_char_text in bad_char:
                    shift += n - bad_char[bad_char_text]
                else:
                    shift += n
            else:
                break
        else:
            # 不匹配，应用坏字符规则
            bad_char_text = text[shift + j]
            print(f"\n  ✗ T[{shift+j}]{bad_char_text} != P[{j}]{pattern[j]}")

            if bad_char_text in bad_char:
                # 坏字符在pattern中
                bad_char_pos = bad_char[bad_char_text]
                move = max(1, j - bad_char_pos)
                shift += move
                print(f"  坏字符'{bad_char_text}'在P中的位置: {bad_char_pos}, 向右移动{move}位")
            else:
                # 坏字符不在pattern中，跳过n位
                shift += n
                print(f"  坏字符'{bad_char_text}'不在P中, 向右移动{n}位")

    print(f"\n匹配位置: {positions}")
    return positions

# 测试
print("\n" + "=" * 60)
print("Boyer-Moore算法（简化版）")
print("=" * 60)

text = "ABAAABABCDEFG"
pattern = "ABCD"
positions = boyer_moore_search(text, pattern)

# 输出：
# ============================================================
# Boyer-Moore算法（简化版）
# ============================================================
# 构建坏字符表:
#   'A': 最右位置=0
#   'B': 最右位置=1
#   'C': 最右位置=2
#   'D': 最右位置=3
#
# 坏字符表: {'A': 0, 'B': 1, 'C': 2, 'D': 3}
#
# 匹配过程:
#
# 偏移0:
#   ✗ T[3]A != P[3]D
#   坏字符'A'在P中的位置: 0, 向右移动3位
#
# 偏移3:
#   ✗ T[6]A != P[3]D
#   坏字符'A'在P中的位置: 0, 向右移动3位
#
# 偏移6: T[9]D==P[3]D T[8]C==P[2]C T[7]B==P[1]B T[6]A==P[0]A
#   ✓ 完全匹配
#
# 匹配位置: [6]

def sunday_search(text, pattern):
    """
    Sunday字符串匹配
    时间：O(mn)最坏, 通常O(m+n)
    空间：O(字符集大小)
    """
    m, n = len(text), len(pattern)

    if n == 0:
        return []
    if m < n:
        return []

    # 预处理：记录pattern中每个字符最右位置
    char_pos = {}

    print("构建字符位置表:")
    for i, char in enumerate(pattern):
        char_pos[char] = i
        print(f"  '{char}': 最右位置={i}")

    print(f"\n字符位置表: {char_pos}\n")

    positions = []
    i = 0  # text中的当前窗口起始位置

    print("匹配过程:")

    while i <= m - n:
        print(f"\n窗口[{i}:{i+n}]: {text[i:i+n]}", end="")

        # 检查是否匹配
        j = 0
        while j < n and text[i+j] == pattern[j]:
            j += 1

        if j == n:
            print(" ✓ 匹配")
            positions.append(i)
        else:
            print(f" ✗ 不匹配（位置{j}: {text[i+j]} != {pattern[j]}）")

        # 查看窗口后的字符
        if i + n < m:
            next_char = text[i + n]
            print(f"  窗口后字符: '{next_char}'")

            if next_char in char_pos:
                # 字符在pattern中
                shift = n - char_pos[next_char]
                print(f"  '{next_char}'在P中位置{char_pos[next_char]}, 向右移动{shift}位")
            else:
                # 字符不在pattern中，跳过n+1位
                shift = n + 1
                print(f"  '{next_char}'不在P中, 向右移动{shift}位")

            i += shift
        else:
            break

    print(f"\n匹配位置: {positions}")
    return positions

# 测试
print("\n" + "=" * 60)
print("Sunday算法")
print("=" * 60)

text = "SUBSTRINGSEARCH"
pattern = "SEARCH"
positions = sunday_search(text, pattern)

# 输出：
# ============================================================
# Sunday算法
# ============================================================
# 构建字符位置表:
#   'S': 最右位置=0
#   'E': 最右位置=1
#   'A': 最右位置=2
#   'R': 最右位置=3
#   'C': 最右位置=4
#   'H': 最右位置=5
#
# 字符位置表: {'S': 0, 'E': 1, 'A': 2, 'R': 3, 'C': 4, 'H': 5}
#
# 匹配过程:
#
# 窗口[0:6]: SUBSTR ✗ 不匹配（位置1: U != E）
#   窗口后字符: 'I'
#   'I'不在P中, 向右移动7位
#
# 窗口[7:13]: SEARCH ✓ 匹配
#   窗口后字符: 'A'
#   'A'在P中位置2, 向右移动4位
#
# 匹配位置: [7]

def is_palindrome(s):
    """
    判断回文串（双指针）
    时间：O(n)
    空间：O(1)
    """
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True

# 测试
print("回文检测:")
print(f"'racecar': {is_palindrome('racecar')}")  # True
print(f"'hello': {is_palindrome('hello')}")      # False

def length_of_longest_substring(s):
    """
    最长无重复子串（LeetCode 3）
    滑动窗口
    """
    char_index = {}
    left = 0
    max_len = 0

    for right, char in enumerate(s):  # enumerate同时获取索引和值
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1

        char_index[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len

# 测试
print("\n最长无重复子串:")
print(f"'abcabcbb': {length_of_longest_substring('abcabcbb')}")  # 3 ("abc")
print(f"'bbbbb': {length_of_longest_substring('bbbbb')}")      # 1 ("b")
print(f"'pwwkew': {length_of_longest_substring('pwwkew')}")     # 3 ("wke")

def prefix_sum_hashes(s):
    """
    字符串前缀哈希（用于快速计算子串哈希）
    """
    n = len(s)
    prefix = [0] * (n + 1)
    power = [1] * (n + 1)
    base = 131
    mod = 2**64

    for i in range(n):
        prefix[i+1] = (prefix[i] * base + ord(s[i])) % mod
        power[i+1] = (power[i] * base) % mod

    return prefix, power

def get_hash(prefix, power, l, r):
    """获取子串[l, r]的哈希"""
    return (prefix[r+1] - prefix[l] * power[r-l+1]) % (2**64)

def longest_common_prefix(strs):
    """
    最长公共前缀（水平扫描）
    时间：O(mn), m=字符串数, n=平均长度
    """
    if not strs:
        return ""

    prefix = strs[0]

    print(f"初始前缀: {prefix}")

    for s in strs[1:]:  # 切片操作：[start:end:step]提取子序列
        print(f"\n比较: '{prefix}' 和 '{s}'")

        while s.find(prefix) != 0:
            prefix = prefix[:-1]
            print(f"  不匹配，缩短前缀: '{prefix}'")

            if not prefix:
                return ""

    print(f"\n最长公共前缀: '{prefix}'")
    return prefix

# 测试
print("\n" + "=" * 60)
print("最长公共前缀")
print("=" * 60)

strs = ["flower", "flow", "flight"]
result = longest_common_prefix(strs)

# 输出：'fl'

def reverse_string(s):
    """
    反转字符串（双指针）
    时间：O(n)
    空间：O(1)
    """
    s = list(s)
    left, right = 0, len(s) - 1

    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

    return ''.join(s)

# 测试
print("\n反转字符串:")
print(f"'hello' → '{reverse_string('hello')}'")  # 'olleh'

def multiply(num1, num2):
    """
    字符串相乘（模拟手工乘法）
    时间：O(mn)
    """
    if num1 == "0" or num2 == "0":
        return "0"

    m, n = len(num1), len(num2)
    result = [0] * (m + n)

    print(f"  {num1}")
    print(f"× {num2}")
    print(f"{'-' * (max(m, n) + 2)}")

    # 从右向左相乘
    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
            p1, p2 = i + j, i + j + 1

            # 加到结果中
            total = mul + result[p2]
            result[p2] = total % 10
            result[p1] += total // 10

    # 转换为字符串
    result_str = ''.join(map(str, result)).lstrip('0')

    return result_str

# 测试
print("\n字符串相乘:")
print(f"123 × 456 = {multiply('123', '456')}")  # "56088"