5

输入：

有一个长字符串S，我们有一个整数数组，A它表示字符串的前缀，S如A[i]表示前缀S[0..A[i]]

输出：

返回一个与和的最长匹配后缀的长度Output[]相同大小的数组AOutput[i]S[0..A[i]]S

样本输入：

S = "ababa"
A[]=[0, 1, 2, 3, 4]

样本输出：

Output[]=[1,0,3,0,5]

我拥有的最幼稚的算法是每个字符串都A[i]匹配两个字符串末尾S[0..A[i]]之间的字符数。S但是这个算法是O(n^2)其中 n 是原始字符串 S 的长度。

问题：
有没有更好的算法对字符串 S 进行预处理，然后可以快速返回整个输入 Array 的最长长度后缀？

4

2 回答 2

4

这只是反转字符串的Z 函数。细微的差别是 Z 函数的第一个元素被选择为等于S的长度。有一种算法可以在O(n)中计算字符串的 Z 函数

这个问题的算法如下：

  • S' := 反转 S
  • Z := S' 的 Z 函数
  • 对于每个i， Output[i] := Z[Len(S) - A[i] - 1]

例如：

S = "baabaaa"
A[] = [0,1,2,3,4,5,6]
Output[] should be [0,1,2,0,1,2,7]

S' = "aaabaab"
Z = Z-function(S') = [7,2,1,0,2,1,0] (with the first element chosen to be Len(S))
于 2015-10-07T08:33:04.363 回答
-1

您正在寻找的算法/数据结构称为后缀树，它的最坏情况复杂度为O(n log n)

在计算机科学中，后缀树（也称为 PAT 树，或者早期形式的位置树）是一个压缩的 trie，包含给定文本的所有后缀作为它们的键和在文本中的位置作为它们的值。后缀树允许特别快速地实现许多重要的字符串操作。（维基）

在这里您可以找到一些详细解释功能和实现的幻灯片

于 2015-10-07T08:29:37.457 回答