请教suffix array的问题# JobHunting - 待字闺中
a*u
1 楼
给一个string建立suffix array，然后sort这些substrings，复杂度是多少？O(nlgn)
or O(n^2lgn)?
比如 String "bananna", size n = 7
suffix array
{
banana
anana
nana
ana
na
a
}
after sorting
{
a
ana
anana
banana
na
nana
}
for a string size n, creating the suffix array is O(n), sorting is supposed
to be O(nlgn), but I somehow feel it is O(n^2lgn), since the comparison
between two substrings are O(n).
Where did I miss?
or O(n^2lgn)?
比如 String "bananna", size n = 7
suffix array
{
banana
anana
nana
ana
na
a
}
after sorting
{
a
ana
anana
banana
na
nana
}
for a string size n, creating the suffix array is O(n), sorting is supposed
to be O(nlgn), but I somehow feel it is O(n^2lgn), since the comparison
between two substrings are O(n).
Where did I miss?
