交付：五条验收条款一起过

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

一段文本 abababcababcabababc（19 个字符，下标从 0 起）和一个模式 ababc：最后一步：把五条验收条款补全，一次全验过。每一条钉的都是换了算法也不该变的那个量。

提交你的答案

请登录后提交答案。

去登录

← 第四步：多模式那一路也要对账「测过了」和「证明了」差在哪 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

T = "abababcababcabababc"
P = "ababc"
WORDS = ['he', 'she', 'his', 'hers']
TXT = "ushershishe"
BASE = 31
MOD = 17
PALS = "abcbdcba"

def brute(t, p):
    return [i for i in range(len(t) - len(p) + 1) if t[i:i + len(p)] == p]

def hs(s):
    h = 0
    for c in s:
        h = (h * BASE + ord(c) - 96) % MOD
    return h

def by_hash(t, p):
    hp = hs(p)
    return [i for i in range(len(t) - len(p) + 1)
            if hs(t[i:i + len(p)]) == hp and t[i:i + len(p)] == p]

def build_next(p):
    f = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k and p[i] != p[k]:
            k = f[k - 1]
        if p[i] == p[k]:
            k += 1
        f[i] = k
    return f

def kmp(t, p):
    f = build_next(p)
    pos = []
    k = 0
    for i in range(len(t)):
        while k and t[i] != p[k]:
            k = f[k - 1]
        if t[i] == p[k]:
            k += 1
        if k == len(p):
            pos.append(i - k + 1)
            k = f[k - 1]
    return pos

def trie_hits(words, txt):
    t = {}
    for w in words:
        node = t
        for ch in w:
            node = node.setdefault(ch, {})
        node["#"] = w
    hits = []
    for i in range(len(txt)):
        node = t
        for j in range(i, len(txt)):
            if txt[j] not in node:
                break
            node = node[txt[j]]
            if "#" in node:
                hits.append((i, node["#"]))
    return sorted(hits)

def longest_pal(s):
    best = ""
    for c in range(2 * len(s) - 1):
        lo, hi = c // 2, c // 2 + c % 2
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        if hi - lo - 1 > len(best):
            best = s[lo + 1:hi]
    return best

# 五条验收条款，每条都钉在一个"换算法也不该变"的量上
c1 = brute(T, P) == [2, 7, 14]                 # 基准线给出这三个位置
c2 = by_hash(T, P) == brute(T, P)              # 哈希版和基准线一致
c3 = None      # TODO: KMP 版也和基准线一致
c4 = None      # TODO: Trie 一次扫过，命中 6 处
c5 = None      # TODO: 前四条全部成立

print("/".join("过" if x else "不过" for x in (c1, c2, c3, c4, c5)))

本次输入：

输出：

👩‍🏫

💬 题目评论

交付：五条验收条款一起过

更多题目

全部评论