P2852 [USACO06DEC]牛奶模式Milk Patterns 后缀数组(poj3261)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n, m, k, p;
int s[maxn];
int sa[maxn], rak[maxn], tx[maxn], height[maxn], q[maxn];
struct node {
  int x, y, id;
}a[maxn],b[maxn];
void rsort() {
  for (int i = 1; i <= m; i++) {
    tx[i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    tx[a[i].y]++;
  }
  for (int i = 1; i <= m; i++) {
    tx[i] += tx[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    b[tx[a[i].y]--] = a[i];
  }
  for (int i = 1; i <= m; i++) {
    tx[i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    tx[b[i].x]++;
  }
  for (int i = 1; i <= m; i++) {
    tx[i] += tx[i - 1];
  }
  for (int i = n; i >= 1; i--) {
    a[tx[b[i].x]--] = b[i];
  }
}
void solve() {
  rsort();
  p = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) {
      ++p;
    }
    rak[a[i].id] = p;
  }
  for (int i = 1; i <= n; i++) {
    a[i].x = rak[i];
    a[i].id = sa[rak[i]] = i;
    a[i].y = 0;
  }
  m = p;
}
void ssort() {
  for (int i = 1; i <= n; i++) {
    a[i].x = a[i].y = s[i];
    a[i].id = i;
    m = max(m, s[i]);
  }
  solve();
  for (int j = 1; j <= n; j <<= 1) {
    for (int i = 1; i + j <= n; i++) {
      a[i].y = a[i + j].x;
    }
    solve();
    if (p == n) {
      break;
    }
  }
}
void get_Height() {
  int k = 0;
  for (int i = 1; i <= n; i++) {
    if (k) {
      k--;
    }
    int j = sa[rak[i] - 1];
    while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) {
      k++;
    }
    height[rak[i]] = k;
  }
}
/*
5 2
1 2 1 2 1
*/
int check(int x) {
  int i = 1;
  while (1) {
    for (; i <= n && height[i] < x; i++);
    if (i > n) {
      break;
    }
    int cnt = 1;
    for (; i <= n && height[i] >= x; cnt++, i++);
    if (cnt >= k) {
      return 1;
    }
  }
  return 0;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &s[i]);
  }
  ssort(); get_Height();
  int l = 1, r = n;
  int ans = 0;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  printf("%d\n", l - 1);
  return 0;
}