一个字符串的前缀，同时也是0 (n)个字符串的前缀

Question

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

现在说我有一个布尔数组，isSuffixPrefix?sizen的，即字符串str的长度。isSuffixPrefix吗?[i]istrue如果字符串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..]你可以反转你想要的单词它会给你一个数组从[n…]但你也需要反转数组本身:

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//作为后缀s[2..]2] = "也是字符串s

的前缀。

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