⚠️ 三种算法，位置必须一个不差

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

一段文本 abababcababcabababc（19 个字符，下标从 0 起）和一个模式 ababc：暴力、哈希、KMP 三种写法都已经给好了。把三个结果对一遍，输出位置和对账结论。

提交你的答案

请登录后提交答案。

去登录

← 🔴 KMP 的回退次数是零 ⚠️ 四个词各跑一次匹配，亏在哪 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

T = "abababcababcabababc"
P = "ababc"
BASE = 31
MOD = 17

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

a = brute(T, P)
b = by_hash(T, P)
c = kmp(T, P)
# TODO: 三个结果必须完全一样，一样就输出「一致」，否则输出「不一致」
verdict = "不一致"

print("/".join(str(x) for x in a) + "/" + verdict)

本次输入：

输出：

👩‍🏫

💬 题目评论

⚠️ 三种算法，位置必须一个不差

更多题目

全部评论