后缀数组学习笔记

前言

后缀数组是一种应用很广的字符串算法。与kmp或AC自动机这类字符串匹配算法不同，后缀数组以及后缀自动机这种后缀数据结构，主要用于解决字符串中与子串有关的问题。

从字符串的后缀角度来考虑，其所有后缀的所有前缀，便是字符串的所有子串，而后缀数组可以在在$O(n)$[DC3算法]或$O(nlogn)$​​​[倍增算法]的时间复杂度里，快速求出每个后缀按照字典序排序后的位置，以及排序后相邻后缀的最长公共前缀。如此一来，我们便可以利用字典序或最长公共前缀等等，来解决与子串有关的大部分问题。

首先是暴力

参照上述我们希望得到的功能，我们可以得到一个最暴力的做法：记录每个后缀字符串并按照字典序排序。但很明显这么拉的复杂度是谁都不想看到的，所以我们需要再进一步。

直接排序相当于是对于两个对象的全部值进行比较，这样显然存在许多冗余的操作。我们可以考虑倍增思想。

对于每一个后缀我们可以设置两个关键词，每次只按照这两个关键词进行排序。