P2852 [USACO06DEC]Milk Patterns G题解

P2852 [USACO06DEC]Milk Patterns G

题意：

正解：这题其实就是求不同后缀间的 有k个后缀 出现相同前缀 的这个前缀的最长长度。可以想到这题是用后缀数组了，其中height数组代表的是sa[i-1]和sa[i]的最长公共前缀长度，相当于是有两个后缀出现相同前缀时这个前缀的最长长度，而这题是针对k来考虑，这样的话，其实能转换成另一个问题了，就是在height数组上，区间长度为k-1，所有区间中最小值的最大值，然后众所周知这是单调队列的经典模板题目。

代码：

#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define PI acos(-1)
#define eps 1e-8
#define rint register int
using namespace std;
typedef long long LL;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<LL, LL> pll;
typedef pair<double, double> pdd;
typedef map<int, int> mii;
typedef map<char, int> mci;
typedef map<string, int> msi;
template<class T>
void read(T &res) {
  int f = 1; res = 0;
  char c = getchar();
  while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
  while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); }
  res *= f;
}
const int ne[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, -1, -1, -1, 1, 1, -1, 1, 1};
const int INF = 0x3f3f3f3f;
const int N = 3e5+10;
const LL Mod = 1e9+7;
const int M = 1e6+10;
int s[N];
LL sa[M], t[M], t2[M], c[M], n;
void build_sa(int m) {
  LL *x = t, *y = t2;
  //基数排序
  _for(0, m, i) c[i] = 0;
  _for(0, n, i) c[x[i]=s[i]]++;
  _for(1, m, i) c[i] += c[i-1];
  for(int i = n-1; i >= 0; --i) sa[--c[x[i]]] = i;
  for(int k = 1, p; k <= n; k <<= 1) {
    p = 0;
    //直接利用sa数组排序第二关键字
    _for(n-k, n, i) y[p++] = i;
    _for(0, n, i) if(sa[i] >= k) y[p++] = sa[i] - k;
    //基数排序第一关键字
    _for(0, m, i) c[i] = 0;
    _for(0, n, i) c[x[y[i]]]++;
    _for(1, m, i) c[i] += c[i-1];
    for(int i = n-1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
    //根据sa和y数组计算新的数组
    _for(0, n, i) x[i] ^= y[i], y[i] ^= x[i], x[i] ^= y[i];
    p = 1; x[sa[0]] = 0;
    _for(1, n, i)
      x[sa[i]] = y[sa[i]]==y[sa[i-1]] && (sa[i]+k<n?y[sa[i]+k]:-1)==(sa[i-1]+k<n?y[sa[i-1]+k]:-1) ? p-1 : p++;
    if(p >= n) break;  //以后即使继续倍增，sa也不会改变，退出
    m = p;  //下次基数排序的最大值
  }
// rak数组表示下标为i的后缀排名是多少
// RMQ(height, rank[j]+1, rank[k])可以知道j和k(rak[j] < rak[k])的最长公共前缀长度
int rak[N], height[N];
void getHeight() {
  int j, k = 0;
  _for(0, n, i) rak[sa[i]] = i;
  _for(0, n, i) {
    if(!rak[i]) continue;
    if(k) --k;
    j = sa[rak[i]-1];
    while(s[i+k] == s[j+k]) ++k;
    height[rak[i]] = k;
  }
}
int k, mx;
deque<int> dq;
int main() {
  scanf("%d %d", &n, &k);
  _for(0, n, i) scanf("%d", &s[i]), mx = max(mx, s[i]);
  build_sa(mx+1); getHeight();
  int ans = 0;
  _for(0, n, i) {
    while(!dq.empty() && dq.front() < i-k+2) dq.pop_front();  
    while(!dq.empty() && height[dq.back()] >= height[i]) dq.pop_back();
    dq.push_back(i);
    if(i >= k-2) ans = max(ans, height[dq.front()]);
  }
  printf("%d\n", ans);
  return 0;
}

本文地址：https://blog.csdn.net/qq_43408978/article/details/108558887