字符串算法详解

def brute_force_search(text, pattern):
    """
    暴力字符串匹配
    :param text: 文本
    :param pattern: 模式串
    :return: 所有匹配位置的列表
    """
    n = len(text)
    m = len(pattern)
    positions = []
    
    # 遍历文本的每个可能起始位置
    for i in range(n - m + 1):
        # 检查从位置 i 开始是否匹配
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        
        if match:
            positions.append(i)
    
    return positions

# 测试
text = "AABAACAADAABAABA"
pattern = "AABA"
print(brute_force_search(text, pattern))  # [0, 9, 12]

def rabin_karp_search(text, pattern, prime=101):
    """
    Rabin-Karp 字符串匹配
    :param text: 文本
    :param pattern: 模式串
    :param prime: 质数（用于哈希）
    :return: 所有匹配位置的列表
    """
    n = len(text)
    m = len(pattern)
    d = 256  # 字符集大小
    
    if m == 0 or n < m:
        return []
    
    # 计算 d^(m-1) % prime
    h = pow(d, m - 1, prime)
    
    # 计算模式和文本第一个窗口的哈希值
    pattern_hash = 0
    text_hash = 0
    
    for i in range(m):
        pattern_hash = (d * pattern_hash + ord(pattern[i])) % prime
        text_hash = (d * text_hash + ord(text[i])) % prime
    
    positions = []
    
    # 滑动窗口
    for i in range(n - m + 1):
        # 哈希值匹配，进一步验证（避免哈希冲突）
        if pattern_hash == text_hash:
            if text[i:i+m] == pattern:
                positions.append(i)
        
        # 计算下一个窗口的哈希值
        if i < n - m:
            text_hash = (d * (text_hash - ord(text[i]) * h) + 
                        ord(text[i + m])) % prime
            # 处理负数
            if text_hash < 0:
                text_hash += prime
    
    return positions

# 测试
text = "AABAACAADAABAABA"
pattern = "AABA"
print(rabin_karp_search(text, pattern))  # [0, 9, 12]

def build_suffix_array(text):
    """
    构建后缀数组
    :param text: 输入字符串
    :return: 后缀数组（排序后的起始位置）
    """
    n = len(text)
    # 生成所有后缀及其起始位置
    suffixes = [(text[i:], i) for i in range(n)]
    # 按字典序排序
    suffixes.sort()
    # 返回起始位置数组
    return [suffix[1] for suffix in suffixes]

def longest_common_prefix(text, suffix_array):
    """计算相邻后缀的最长公共前缀"""
    n = len(text)
    sa = suffix_array
    lcp = [0] * n
    
    for i in range(1, n):
        # 计算 sa[i-1] 和 sa[i] 对应后缀的 LCP
        k = 0
        while (sa[i-1] + k < n and sa[i] + k < n and 
               text[sa[i-1] + k] == text[sa[i] + k]):
            k += 1
        lcp[i] = k
    
    return lcp

# 测试
text = "banana"
sa = build_suffix_array(text)
print("后缀数组:", sa)
# [5, 3, 1, 0, 4, 2]
# 对应后缀: a, ana, anana, banana, na, nana

def manacher(s):
    """
    Manacher 算法求最长回文子串
    :param s: 输入字符串
    :return: 最长回文子串
    """
    # 预处理：插入特殊字符，统一奇偶长度
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    
    # p[i] 表示以 t[i] 为中心的最长回文半径
    p = [0] * n
    center = right = 0
    max_len = max_center = 0
    
    for i in range(n):
        # 利用对称性
        if i < right:
            mirror = 2 * center - i
            p[i] = min(right - 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] > right:
            center = i
            right = i + p[i]
        
        # 更新最长回文
        if p[i] > max_len:
            max_len = p[i]
            max_center = i
    
    # 提取最长回文子串
    start = (max_center - max_len) // 2
    return s[start:start + max_len]

# 测试
print(manacher("babad"))    # "bab" 或 "aba"
print(manacher("cbbd"))     # "bb"
print(manacher("racecar"))  # "racecar"

def find_dna_motif(dna_sequence, motif):
    """在 DNA 序列中查找基序"""
    return kmp_search(dna_sequence, motif)

# 测试
dna = "ATCGATCGATCGATCG"
motif = "ATCG"
positions = find_dna_motif(dna, motif)
print(f"基序 '{motif}' 出现在位置: {positions}")