string - 不同回文子串的数量

Question

给定一个字符串，我知道如何使用 Manacher 算法在线性时间内找到回文子串的数量。但现在我需要找到 distinct/unique 回文子串的数量。现在，这可能会导致 O(n + n^2) 算法 - 一个“n”用于查找所有此类子字符串，n^2 用于将这些子字符串中的每一个与已经找到的子字符串进行比较，以检查它是否唯一。

我确信有一种算法具有更好的复杂性。我在考虑用后缀树试试运气？有没有时间复杂度更好的算法？

Answer 1

我只会将您找到的子字符串放入哈希表中，以防止两次保存相同的结果。

哈希表的访问时间是O(1)。