问题描述
给定一个字符串，我知道如何寻找的回文子的线性时间使用Manacher算法的数量。但现在我需要找到的不同的/独特的回文子串的数量。现在，这可能会导致一个O（N + N ^ 2）算法 - 一个'N'寻找所有这些子，和n ^ 2，比较每个子与已发现的，以检查它是否是唯一的。
Given a string, I know how to find the number of palindromic substrings in linear time using Manacher's algorithm. But now I need to find the number of distinct/unique palindromic substrings. Now, this might lead to an O(n + n^2) algorithm - one 'n' for finding all such substrings, and n^2 for comparing each of these substrings with the ones already found, to check if it is unique.
我相信有一个算法具有较好的复杂性。我在想，也许想我的运气后缀树？是否有一个算法具有较好的时间复杂度？
I am sure there is an algorithm with better complexity. I was thinking of maybe trying my luck with suffix trees? Is there an algorithm with better time complexity?
推荐答案
我只想让你发现到哈希表子以prevent控股两次相同的结果。
I would just put substrings you found into the hash table to prevent holding the same results twice.
的存取时间哈希表为O（1）。
The access time to hash table is O(1).
这篇关于鲜明的回文子串数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！