🔴 预处理的成本，摊到十段文本上还剩多少

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

模式固定是 ababc，文本一段接一段地来，每段都长 abababcababcabababc 那样。next 表只需要算一次。算出「1 段」和「10 段」时两种做法各要比多少次，按暴力1 / 暴力10 / KMP1 / KMP10 的顺序输出。

提交你的答案

请登录后提交答案。

去登录

← ⚠️ 需求没说清时，该回答什么交付一个匹配实现，先验哪一样 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

T = "abababcababcabababc"
P = "ababc"

def brute_cmp(t, p):
    c = 0
    for i in range(len(t) - len(p) + 1):
        j = 0
        while j < len(p):
            c += 1
            if t[i + j] != p[j]:
                break
            j += 1
    return c

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

def kmp_cmp(t, 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
    c = 0
    k = 0
    for i in range(len(t)):
        while k and t[i] != p[k]:
            k = f[k - 1]
            c += 1
        c += 1
        if t[i] == p[k]:
            k += 1
        if k == len(p):
            k = f[k - 1]
    return c

def total(kind, n_texts):
    # TODO: 'brute' → 每段文本都花 brute_cmp(T, P)，没有预处理
    # TODO: 'kmp'   → next 表**只算一次**，之后每段文本花 kmp_cmp(T, P)
    return -1

print("/".join(str(total(k, n)) for k in ("brute", "kmp") for n in (1, 10)))

本次输入：

输出：

👩‍🏫

💬 题目评论

🔴 预处理的成本，摊到十段文本上还剩多少

更多题目

全部评论