后缀数组其实概念很好理解，就是给出一个字符串，长度是n，对它所有的n个后缀编号从1到n进行排序，排序后，最小的那个后缀的编号假设是m1，那么sa[1] = m1，类似地，第二小的是m2的话，sa[2] = m2，sa这个数组就是我们所需要的后缀数组。根据这个，我们可以直接用sort算出sa，以下为最简单的实现
struct SA_simple { vector<int> sa; int s_size; const char* p_s; int size() const { return s_size; } static bool cmp(const char* x, const char* y) { return strcmp(x, y) < 0; } void init(char * str) { int n = strlen(str); s_size = n; p_s = str - 1; sa.resize(n + 1); vector< const char* > rp; rp.resize(n + 1); for (int i = 1; i <= n; ++i) { rp[i] = p_s + i; } sort(rp.begin() + 1, rp.end(), cmp); for (int i = 1; i <= n; ++i) { sa[i] = rp[i] - p_s; } } }; 这个实现的时间复杂度 $O(n^2logn)$
要注意的一点是下标从1开始。有了这个，可以做点什么呢？例如给你一个串p，求出p在主串s中出现了多少次。那么在有了sa的情况下，因为sa是有序的，问题就变成了二分搜索，分别用lower_bound和upper_bound通过sa搜索p，两个相减便得出现次数。