劳资终于搞懂后缀数组啦！！！
#include "cstdio" inline int readStr( char* s ) { static int len; static char ch; len = 0; while((ch = (char) getchar()) == ' ' || ch == '\n'); do s[len++] = ch; while((ch = (char) getchar()) != ' ' && (ch ^ 10) && (ch ^ -1)); return len; } #define P 20 #define MAXN 100005 #define min(a, b) ((a) < (b) ? (a) : (b)) typedef class Suffix_Array { private: short flag = 0; int n, a[MAXN], b[MAXN], c[MAXN], sa[MAXN], height[MAXN], rank[MAXN], log2[MAXN], st[MAXN][P]; inline void Rmq_Init(int* a, int n) { for(register int i = 2; i <= n; ++i) log2[i] = log2[i >> 1] + 1; for(register int i = 0; i <= n; ++i) st[i][0] = a[i]; for(register int i, j = 1, len; j <= log2[n]; ++j) for(i = 0, len = (1 << j); i + len - 1 <= n; ++i) st[i][j] = min(st[i + (len >> 1)][j - 1], st[i][j - 1]); } inline int Ask_Rmq(int l, int r) { static int k; if(l > r) { l ^= r ^= l ^= r; } k = log2[r - l + 1]; return min(st[l][k], st[r - (1 << k) + 1][k]); } public: void build(char* s, int n, int m) { int *x = a, *y = b, *t; this -> n = n; for(register int i = 0; i < m; c[i++] = 0); for(register int i = 0; i < n; ++c[x[i] = s[i++]]); for(register int i = 1; i < m; ++i) c[i] += c[i - 1]; for(register int i = n - 1; ~i; sa[--c[x[i]]] = i--); for(register int i, k = 1, p = 1; p < n && k <= n; k <<= 1, m = p) { for(p = 0, i = n - k; i < n; y[p++] = i++); for(i = 0; i < n; sa[i] >= k ? y[p++] = sa[i++] - k : ++i); for(i = 0; i < m; c[i++] = 0); for(i = 0; i < n; ++c[x[y[i++]]]); for(i = 1; i < m; ++i) c[i] += c[i - 1]; for(i = n - 1; ~i; sa[--c[x[y[i]]]] = y[i--]); for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i) x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p - 1 : p++; } for(register int i = 0; i < n; rank[sa[i]] = i++); for(register int i = 0, k = 1, j; i < n; height[rank[i++]] = k) for(--k, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; ++k); } inline int Lcp(int l, int r) { if( !flag ) { Rmq_Init(height, n); flag = 1; } return Ask_Rmq(rank[l] + 1, rank[r]); } } Suffix; char s[MAXN]; Suffix Sa; int main() { }