不同的迴文子串的數量

給定一個字符串，我知道如何使用Manacher算法在線性時間內找到迴文子串的個數。但是現在我需要找到不同的/唯一的迴文子串的數目。現在，這可能導致O（n + n^2）算法 - 找到所有這樣的子字符串爲'n'，並且用n^2比較每個這些子字符串與已經找到的子字符串，以檢查它是否是唯一的。不同的迴文子串的數量

我相信有一個算法具有更好的複雜性。我想也許試着用後綴樹來運氣？有更好的時間複雜度的算法嗎？

來源

2013-12-09 Liam Willis

不比較每個元素與其他元素是否導致n2？所以我認爲它應該是O（n + n 2）= O（n 2）。儘管如此，我同意這一點仍然非常糟糕。 – CompuChip

@CompuChip是的，我的壞。編輯它。 –

我只是把你發現的子串放在哈希表中，以防止兩次保持相同的結果。

哈希表的訪問時間爲O（1）。

來源

2013-12-09 14:52:49 zavg

我知道如何在線性時間內找到_number_這樣的子字符串，而不是子字符串本身。基本上我在談論Manacher算法。 –

@LiamWillis：維基百科http://en.wikipedia.org/wiki/Longest_palindromic_substring沒有提及* number *，但明確指出：*然而，正如Apostolico，Breslauer＆Galil（1995）所觀察到的，同樣的算法可以也可用於在輸入字符串中的任意位置查找所有最大回文子字符串，再次以線性時間。*注意在此句子中使用字** find **。我很困惑。 –

在相同的Manacher算法中，當您找到圍繞中心的子字符串時，只需按照@zavg所建議的將其存儲在哈希表中即可。 –

不同的迴文子串的數量

回答

相關問題