等于后缀的前缀数

Question

我试图在长度为 n 的字符串中找到等于后缀的前缀数及其长度。它们可以重叠，例如，如果字符串是 "abacaba"，则 ans 是长度为 1 (a) 的 {1, 3, 7} 前缀，3 是 "aba" 和整个字符串。前缀 "a" 等于后缀 "a"。前缀 "aba" 等于后缀 "aba"。整个字符串等于后缀。如果字符串是 "aaaaa" 那么答案是 {1, 2, 3, 4, 5}。 "a", "aa", "aaa", "aaaa", "aaaaa".

我只能在 O(n2) 中获得，其中我们获取每个前缀并与相同长度的后缀进行比较。但是有没有更好的算法来解决这个问题呢？提前致谢

Answer 1

散列法在这里可以提供帮助

定义字符串a1a2a3a4的哈希函数为(a1 * 26^3 + a2 * 26^2 + a3 * a6^1 + a4 * 26^0) % M 其中M为大素数

现在保留两个指针，一个在开头，一个在结尾。在每次迭代中向前移动起始指针并计算前缀的哈希值以开始并在每次迭代中向后移动结束指针并计算后缀的哈希值，如果哈希值相等则字符串相等。

hash_st = 0
hash_ed = 0
st = 0
ed = len(s)-1
while st ! = len(s) - 1:
    hash_st = (hash_st*(26) + ascii_val(s[st])) % M
    hash_ed = (ascii_val(s[ed]) * (26^st) + hash_ed) % M
    if hash_st == hash_ed:
        add_to_result(st)

Answer 2

我的方法用 O(N) 时间预处理字符串，然后用 O(|ans 数组|) 计算答案。

预处理基本上是 KMP 失败 table 构建部分，在除最后一个字符外的整个字符串上。（"abacab" 在你的例子中）。在之前返回的 table 中，给定字符串中最后一个索引的值（即 5 或 'b'）将为 2。这意味着与以 'b' 结尾的 AND 匹配的最大前缀是 2。现在，如果您的最后一个字符与前缀的第 3 个字符 ('a') 匹配，则您的后缀等于前缀。 ("aba")

KMP 停在那里。但是你想要所有的比赛。因此，您需要找到前缀以 'b' 结尾的所有匹配，而不是以最后一个字符结尾的最大匹配（'b' 中的 2 个）。因此，您继续进入 KMP 的内部循环，并且像上面一样，检查当前以 'b' 结尾的匹配项数量（可以为零），如果下一个字符等于我们的最后一个字符。

def build_table(pat):
    table = [0]*len(pat)
    p = 0
    for i in range(1,len(pat)):
        while p>0 and pat[p]!=pat[i]: #KMP's loop i was talking about
            p = table[p-1]

        if pat[p]==pat[i]:
            table[i] = p+1
            p+=1

    return table

pat = "abracadabab"
table = build_table(pat[:-1]) #build table for "abracadaba", i.e except last 

ans = [] #to store answers
p = len(pat)-1 #last index of table building string i.e 5 or 'b'
while p>0: #the main loop
    p = table[p-1] 
    print(p)
    if pat[p]==pat[-1]:
        ans.append(p+1)

print(ans)

"abacab" 打印 [1,3]，"abracadabra" 打印 [1,4]。将整个长度视为特殊情况。

(注意我的 while 循环和 KMP 循环之间的相似性。如果你仍然感到困惑，我强烈建议彻底 read/understand KMP。这很容易得到一个整体的想法，但是深入理解对于回答这样的问题真的很难而且很重要。）

等于后缀的前缀数

number of prefixes equal to suffixes

string

algorithm

suffix