在字符串处理中，非空字符串若其长度为1或其最长边界恰好出现两次，则称为闭合字符串。若一个闭合子串无法在左右两侧扩展而保持闭合性，则称为最大闭合子串（MCS）。MCS可以被视为一种包含重复结构的最大类，包括run。在本文中，我们研究了如何在线计算字符串的MCS，即每次追加一个字符时进行计算。
我们的算法通过使用后缀的最右侧先前出现位置来检测新形成的MCS。为此，我们引入了一种新型数据结构——链接切割后缀树（LCST），它将在线后缀树与链接切割树结合。LCST在总时间复杂度为 $O(n \log n)$ 和空间复杂度为 $O(n)$ 的情况下，维护了后缀树中子串的最右侧出现信息，其中 $n$ 为输入字符串的长度。
利用LCST，我们获得了一个 $O(n \log n)$ 时间复杂度的在线算法，用于计算所有的MCS，这在最坏情况下是最优的。此外，LCST的直接应用还包括右侧LZ77分解和最新匹配查询的在线算法。
博主点评： 本文提出的LCST数据结构为在线字符串处理提供了新的思路，尤其在实时计算最大闭合子串时展现了优越性。其在空间和时间上的优化，使得处理长字符串时更加高效，具有广泛的应用前景。