后缀数组基本定义

在字符串处理中，子串 S 的一个子串 r[i..j]，定义为从索引 i 到 j 的连续字符组成，即 r[i]、r[i+1]...r[j]。特别地，后缀指的是从一个特定位置 i 开始到串尾的子串，记作 Suffix(i)，即 Suffix(i)=r[i..len(r)]。大小比较则是按照常规的“字典顺序”，即逐字符比较 u[i] 与 v[i]，如果相等则继续，否则根据 u[i] 和 v[i] 的大小关系判断 u 和 v 的大小。由于后缀的长度不同，两个不同开头位置的后缀比较不可能相等，除非它们完全相同。

后缀数组 SA 是一个一维数组，其中包含 1 到 n 的排列，如 SA[1], SA[2], ..., SA[n]，并且满足 Suffix(SA[i]) 小于 Suffix(SA[i+1])，其中 1 ≤ i < n。这个数组将 S 的所有后缀按照从小到大的顺序排列，然后将排序后的索引顺序存入 SA。与之相对的是名次数组 Rank，它记录了每个后缀在所有后缀中的顺序，即“你是第几位”。

简单来说，后缀数组回答的是“哪个后缀排在第几位”，而名次数组则告诉你“你排在第几位”。两者是互补的，一旦计算出一个，另一个可以通过常数时间快速得出。如果字符串长度为 n，为了便于大小比较，通常会在字符串末尾添加一个特殊字符。求出名次数组后，可以快速比较任意两个后缀，而直接比较两个后缀的大小，最坏情况下只需比较 n 次字符即可得出结果。

简单的讲，“一府”是指人民政府，“两院”是指人民法院、人民检察院。在中国，国家行政机关、审判机关、检察机关都由作为国家权力机关的人民代表大会产生，对它负责，受它监督；国家机构按照民主集中制的原则活动。