string - 具有后缀树的最短不可重复子串

Question

我需要设计一种有效的算法来找到文本中最短的不可重复子字符串。在本质上; 在文本中只出现一次的最短字符串。只能使用 suffix-tree

示例 1：

Text: AATGCCTA然后 Result: G

示例 2：

Text: AAAAGGGG然后 Result: AG

标签： stringalgorithmbioinformaticssuffix-tree

Answer 1

shortes 不可重复子串是所有后缀中最短的唯一前缀。

请参阅Lucian Ilie 和 WF Smyth 的最小唯一子串和最大重复次数。