字符串的后缀也是 O(n) 中同一字符串的前缀

Question

最近在HackerEarth平台上遇到了一个问题，解决问题的主要思路是在线性时间中查找一个字符串的哪些后缀也是同一个字符串的前缀（以字符串的大小）。例如，在字符串“abcdzyabc”中，“abc”是该字符串的后缀，也是它的前缀。我们需要在线性时间内找到所有这样的后缀。

现在假设我有一个布尔数组，isSuffixPrefix?，大小为 n，即字符串的长度 str 。 isSuffixPrefix?[i] 是 true 如果字符串 str 的后缀从索引 i即后缀str[i...n-1]也是同一个字符串str的前缀，它否则为 false。我们如何在线性时间（如果可能）内计算这个数组？

字符串示例 s = "aaa":

isSuffixPrefix?[0] = true    // as suffix s[0..2] = "aaa" is also the prefix of string s
isSuffixPrefix?[1] = true    // as suffix s[1..2] = "aa" is also the prefix of string s
isSuffixPrefix?[2] = true    // as suffix s[2..2] = "a" is also the prefix of string s

Answer 1

你的问题不完全是前缀函数，因为前缀函数被定义为长度为 n 的数组 π，其中 π[i] 是子串 s[0…i] 的最长正确前缀的长度也是此子字符串的后缀 而不是整个字符串 但您可以稍微调整一下功能以获得您想要的。因为前缀函数来自 [0..i] 你可以反转你想要的词，它会从 [n...i] 给你数组但是你也需要反转数组本身：


def pi_prefix_suffix(pattern):
    P = list(pattern)
    m = len(pattern)
    a = [0] * m
    k = 0

    for q in range(2, m + 1):
        while k > 0 and P[k] != P[q - 1]:
            k = a[k - 1]
        if P[k] == P[q - 1]:
            k += 1
        a[q - 1] = k

    return a;
def reverse_string(x):
  return x[::-1]
  
print("abcbabacba")
print(reverse_string(pi_prefix_suffix(reverse_string("abcbabacba"))));

输出：

abcbabacba
[1, 0, 3, 2, 1, 2, 1, 0, 0, 0]

最后一件事，你说过

isSuffixPrefix?[2] = true // as suffix s[2..2] = "a" is also the prefix of string s

但这在正式方式中是不正确的，因为后缀和前缀不能是整个单词（特别是如果单词是一个字母），根据定义它必须是单词的一部分，如果你愿意的话考虑整个单词，这意味着任何前缀也是单词的后缀。（如果你还想考虑最后一个字母，只需在数组上加 1，因为它总是正确的）

字符串的后缀也是 O(n) 中同一字符串的前缀

Suffixes of a string that are also prefix of the same string in O(n)

string

algorithm

prefix

suffix