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

Question

输入：

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

输出：

Return 与 A 大小相同的数组 Output[] 其中 Output[i] 是 S[0..A[i]] 和 [= 的最长匹配后缀的长度11=]

示例输入：

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进行预处理，然后可以快速return整个输入数组的最长长度后缀？

Answer 1

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

In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations. (wiki)

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

Answer 2

这只是一个Z-function的反转字符串。略有不同的是，Z 函数的第一个元素被选择为等于 S 的长度。有一种算法可以计算O(n)

中字符串的Z函数

而这道题的算法如下：

S' := 反转 S
Z := S'的 Z 函数
对于每个 i，输出[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))

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

Algorithm to find the length of longest suffix between a String and a prefix of the String

java

arrays

string

algorithm

suffix