查找给定单词的双子词的算法

Question

给定词 V 的子词 U 是双子词，当它的形式为 u=ww 时，例如“abab”是“acdababx”的双子词，但“cdab”不是。

我需要一种算法来检查单词 V 的给定子词 U 是否为 double 。 V 可以在线性时间内进行预处理，但是任何特定 U 的答案都应该具有恒定的时间复杂度，因为每个 V 都会有很多 U。U 以间隔给出，例如如果 V = "acdababx"， interval [3..6] 对应子词“daba”。

示例输入和输出:

V = 阿巴巴卡

你=

• [1 4] --> 否
• [3 8] --> 是
• [5 8] --> 否
• [8 9] --> 是
• [1 10] --> 否

这不是任何当前比赛的问题。

Answer 1

这是一种算法，它声称在输入词的后缀树(可以在 O(n) 中构造)中标记所有双词的端点(或者在文献中众所周知，串联重复)时间。当然，由于我没有完全访问该文章，我不确定它是否满足 O(1) 查询时间。

论文是:Linear time algorithms for finding and representing all the tandem repeats in a string

希望对您有所帮助。