算法找到最长后缀的字符串和所述字符串的前缀之间的长度

还有很长的字符串S，我们有整数A的阵列，其表示字符串S的前缀像A[i]表示前缀S[0..A[i]]

输出：

返回为0相同的大小的数组其中Output[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，然后可以快速返回长度最长后缀为整个输入数组？

来源

2015-10-07 pgiitu

你能解释一下'S [1..A [i]]应该是什么吗？从'1'到'A [i]'的子字符串？ – Tim

对不起更新了这个问题。它应该是'S [0..A [i]]'这是从'0'到'A [i]'的子字符串S – pgiitu

@Tim - 从位置'0'到位置'A [i]的子字符串''在'S'中。 –

这仅仅是颠倒字符串的Z-function。略有不同的是，Z函数的第一个元素被选择为等于S的长度。有一种算法来计算在为O（n）

而且算法针对此问题是如下字符串的Z-功能：

S”：=反S
ž ：= Z-函数为每个我的S”
，输出[I]：= Z [LEN（S） - A [1] - 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-07 08:33:04 Kolmar

-1

你正在寻找被称为后缀树算法/数据结构它的O(n log n)

在计算机科学中最糟糕的情况复杂，后缀树（也称为PAT树，或者在更早表格，位置树）是一个压缩树，其中包含给定文本的所有后缀作为它们的键和文本在它们的值的位置。后缀树允许特别快速的实现许多重要的字符串操作。（wiki）

Here你可以找到一些幻灯片，其解释的功能和实行详细

来源

2015-10-07 08:29:37 Westranger

算法找到最长后缀的字符串和所述字符串的前缀之间的长度

回答

相关问题