17. 字符串算法

def naive_match(text, pattern):
    n, m = len(text), len(pattern)
    res = []
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            res.append(i)
    return res

print(naive_match("ABABABCABAB", "ABABC"))  # [2]

def compute_pi(pattern):
    m = len(pattern)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]          # 回退到次长候选前缀
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

print(compute_pi("ABABCABAB"))  # [0, 0, 1, 2, 0, 1, 2, 3, 4]

def kmp_match(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0:
        return []
    pi = compute_pi(pattern)
    res = []
    j = 0                                  # 已匹配的模式串长度
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]                  # 失配时按 next 跳转，不回退 i
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            res.append(i - m + 1)
            j = pi[j - 1]                  # 找下一个匹配
    return res

print(kmp_match("ABABABCABAB", "ABABC"))   # [2]

# 坏字符表：记录每个字符在 pattern 中最后一次出现的下标
def build_bad_char(pattern):
    last = {}
    for i, ch in enumerate(pattern):
        last[ch] = i          # 后出现的覆盖前面的，得到最右位置
    return last

def bm_search(text, pattern):
    last = build_bad_char(pattern)
    n, m = len(text), len(pattern)
    i = 0
    res = []
    while i <= n - m:
        j = m - 1
        while j >= 0 and text[i + j] == pattern[j]:
            j -= 1
        if j < 0:
            res.append(i)
            i += 1 if m == 1 else (m - last.get(text[i + m], -1) if i + m < n else 1)
        else:
            shift = j - last.get(text[i + j], -1)
            i += max(1, shift)
    return res

BASE, MOD = 131, 2**64

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return []
    # 预计算 base^(m-1)
    power = pow(BASE, m - 1, MOD)
    # 计算 pattern 与 text[0:m] 的哈希
    target = 0
    for ch in pattern:
        target = (target * BASE + ord(ch)) % MOD
    h = 0
    for ch in text[:m]:
        h = (h * BASE + ord(ch)) % MOD
    res = []
    for i in range(n - m + 1):
        if h == target:
            if text[i:i + m] == pattern:      # 哈希相等，逐字符确认
                res.append(i)
        if i + m < n:
            h = ((h - ord(text[i]) * power) * BASE + ord(text[i + m])) % MOD
    return res

print(rabin_karp("ABABABCABAB", "ABABC"))     # [2]

def manacher(s):
    # 插入分隔符，统一奇偶
    t = "#" + "#".join(s) + "#"
    n = len(t)
    p = [0] * n            # p[i] 为以 i 为中心的回文半径（含中心）
    center, right = 0, 0
    for i in range(n):
        mirror = 2 * center - i
        if i < right:
            p[i] = min(right - i, p[mirror])   # 借用镜像回文半径
        # 中心扩展
        while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and \
              t[i - p[i] - 1] == t[i + p[i] + 1]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]        # 更新最右边界
    # 还原最长回文（分隔符不计入）
    best, best_c = 0, 0
    for i in range(n):
        if p[i] > best:
            best, best_c = p[i], i
    start = (best_c - best) // 2
    return s[start:start + best]

print(manacher("babad"))    # "bab"（"aba" 亦可）
print(manacher("cbbd"))     # "bb"

class TrieNode:
    __slots__ = ("children", "is_end", "count")
    def __init__(self):
        self.children = {}
        self.is_end = False      # 是否为一个完整单词的结尾
        self.count = 0           # 以该节点为前缀的单词数

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
            node.count += 1
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            node = node.children.get(ch)
            if node is None:
                return False
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return False
        return True

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int next[26];            // 子节点
    int fail;                // 失配指针
    int end;                 // 以该节点结尾的模式串个数
    Node() { memset(next, -1, sizeof next); fail = end = 0; }
};

vector<Node> tr;

void insert(const string& s) {
    int u = 0;
    for (char c : s) {
        int id = c - 'a';
        if (tr[u].next[id] == -1) {
            tr[u].next[id] = tr.size();
            tr.emplace_back();
        }
        u = tr[u].next[id];
    }
    tr[u].end++;
}

void build_automaton() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (tr[0].next[i] != -1) q.push(tr[0].next[i]);
        else tr[0].next[i] = 0;             // 空边指向根
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int v = tr[u].next[i];
            if (v != -1) {
                tr[v].fail = tr[tr[u].fail].next[i];
                tr[v].end += tr[tr[v].fail].end;   // 累加后缀的命中数
                q.push(v);
            } else {
                tr[u].next[i] = tr[tr[u].fail].next[i];  // 压缩失配转移
            }
        }
    }
}

int query(const string& text) {
    int u = 0, ans = 0;
    for (char c : text) {
        u = tr[u].next[c - 'a'];
        ans += tr[u].end;                    // 加上所有以该状态结尾的模式串
    }
    return ans;
}

# 使用 Python 内置哈希做单词频次统计
from collections import Counter

def word_frequency(words):
    return Counter(words)

# 双哈希布隆过滤器示意：k 个哈希位都被置位则认为"可能存在"
class BloomFilter:
    def __init__(self, size, k=3):
        self.bits = [0] * size
        self.k = k

    def _positions(self, item):
        # 用两个基础哈希推导 k 个独立位置
        h1, h2 = hash(item), hash(item + "salt")
        return [(h1 + i * h2) % len(self.bits) for i in range(self.k)]

    def add(self, item):
        for p in self._positions(item):
            self.bits[p] = 1

    def contains(self, item):
        return all(self.bits[p] for p in self._positions(item))