后缀数组与最长公共字串

01后缀数组概述

后缀数组是将字符串所有后缀按字典序排列的数组，输入文本串t[0..n-1]，输出数组sa[0..n-1]，满足后缀严格递增。后缀数组的定义后缀数组兼具后缀树功能，却更省内存，将高维字符串检索转化为一维整数排序，适用于多种字符串问题。后缀数组的优势后缀数组广泛应用于生物信息学、搜索引擎、数据压缩等领域，是这些领域中不可或缺的工具。应用场景

直接排序构造法的瓶颈直接对所有后缀排序，每次比较最坏需O(n)时间，总复杂度升至O(n2logn)，难以突破平方瓶颈。01仅优化排序算法无法突破平方瓶颈，必须改变比较方式或利用字符串自身结构。02改进方向直接排序的