⚠️ 一次扫过 vs 各扫一遍

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

四个要找的词 he、she、his、hers，一段文本 ushershishe（11 个字符，下标从 0 起）：两种做法都写好了。对一下结果，再把两种做法要看的字符数各算出来。

提交你的答案

请登录后提交答案。

去登录

← ⚠️ 哪个位置同时命中了两个词回文子串和回文子序列，哪个更难凑出来 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

WORDS = ['he', 'she', 'his', 'hers']
TXT = "ushershishe"

def build(words):
    t = {}
    for w in words:
        node = t
        for ch in w:
            node = node.setdefault(ch, {})
        node["#"] = w
    return t

def scan(t, txt):
    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 one_by_one(words, txt):
    """每个词各扫一遍文本"""
    hits = []
    for w in words:
        for i in range(len(txt) - len(w) + 1):
            if txt.startswith(w, i):
                hits.append((i, w))
    return sorted(hits)

a = scan(build(WORDS), TXT)
b = one_by_one(WORDS, TXT)
# TODO: 两种做法的命中必须完全一样，一样输出「一致」，否则「不一致」
verdict = "不一致"
# TODO: 一次扫过要看的字符数是 len(TXT)；各扫一遍是 len(TXT) * len(WORDS)
scan_once, scan_each = -1, -1

print(str(len(a)) + "/" + verdict + "/" + str(scan_once) + "/" + str(scan_each))

本次输入：

输出：

👩‍🏫

💬 题目评论

⚠️ 一次扫过 vs 各扫一遍

更多题目

全部评论