后缀数组+单调队列
注意：后缀数组的所有后缀中包括空串，因此有strlen(s)+1个后缀。
View Code #include#include #include #include using namespace std;#define N 20005struct Elem{ int pos, value; Elem() {} Elem(int pp, int vv): pos(pp), value(vv) {}}q[N];int n, m;int s[N];// N > 256int sa[N], height[N], rank[N], tmp[N], top[N];void input(){ scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", &s[i]);}void makesa(int n){ // O(N * log N) int i, j, len, na; na = (n < 256 ? 256 : n); memset(top, 0, na * sizeof(int)); for (i = 0; i < n; i++) top[rank[i] = s[i] & 0xff]++; for (i = 1; i < na; i++) top[i] += top[i - 1]; for (i = 0; i < n; i++) sa[--top[rank[i]]] = i; for (len = 1; len < n; len <<= 1) { for (i = 0; i < n; i++) { j = sa[i] - len; if (j < 0) j += n; tmp[top[rank[j]]++] = j; } sa[tmp[top[0] = 0]] = j = 0; for (i = 1; i < n; i++) { if (rank[tmp[i]] != rank[tmp[i - 1]] || rank[tmp[i] + len] != rank[tmp[i - 1] + len]) top[++j] = i; sa[tmp[i]] = j; } memcpy(rank, sa, n * sizeof(int)); memcpy(sa, tmp, n * sizeof(int)); if (j >= n - 1) break; }}void lcp(int n){ // O(4 * N) int i, j, k; for (j = rank[height[i = k = 0] = 0]; i < n - 1; i++, k++) while (k >= 0 && s[i] != s[sa[j - 1] + k]) height[j] = (k--), j = rank[sa[j] + 1];}void push(Elem a, int front, int &rear){ while (rear > front && a.value <= q[rear - 1].value) rear--; q[rear++] = a;}int work(){ int front = 0, rear = 0; for (int i = 1; i < m; i++) push(Elem(i, height[i]), front, rear); int ret = q[front].value; for (int i = m; i <= n; i++) { while (front != rear && q[front].pos <= i - m + 1) front++; push(Elem(i, height[i]), front, rear); ret = max(ret, q[front].value); } return ret;}int main(){ //freopen("t.txt", "r", stdin); input(); makesa(n + 1); lcp(n + 1); printf("%d\n", work()); return 0;}