题解

题目大意 给你一个长度为n的序列 找出序列出现K次以上的最长后缀

使用后缀自动机将所有后缀排序 获得height数组 用set区间求最小值遍历一遍即可

AC代码

#include <stdio.h> #include <iostream> #include <set> #include <algorithm> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 1e6 + 10; int a[MAXN]; int n, r; //n字符串长度 r基数 int sa[MAXN]; //排名为i的后缀位置+1 i取值1~n int cnt[MAXN]; //基数排序辅助数组 int rak[MAXN]; //第i个后缀的排名 int tmp[MAXN]; //rak的辅助数组 int heig[MAXN]; //后缀排序相邻LCP void radix_sort(int *rk, int *tp) { for (int i = 0; i <= r; i++) //清零 cnt[i] = 0; for (int i = 1; i <= n; i++) //统计各桶要装入的数据个数 cnt[rk[tp[i]]]++; for (int i = 1; i <= r; i++) //合并计算各个桶最后的数字下标索引 cnt[i] += cnt[i - 1]; for (int i = n; i >= 1; i--) //入桶 倒序保证稳定性 sa[cnt[rk[tp[i]]]--] = tp[i]; //按照上次排序结果tmp保证稳定性的情况下再次根据rak排序 } void suffix(int *a) { int *rk = rak, *tp = tmp; //用指针指向两个数组以便后面交换数组 for (int i = 1; i <= n; i++) rk[i] = a[i - 1], tp[i] = i; //初始化 rak、tmp为默认顺序 r = 1e6 + 5; //char 0-127不算汉字 radix_sort(rk, tp); for (int l = 1, p = 1, i; p < n; l <<= 1, r = p) //l + 1为当前子串长度 当p排序不同数量大于等于n时退出 { //当前的tmp直接由上次的sa得到 for (p = 0, i = n - l + 1; i <= n; i++) //长度越界后补0 tp[++p] = i; for (i = 1; i <= n; i++) if (sa[i] > l) tp[++p] = sa[i] - l; radix_sort(rk, tp); //更新sa swap(rk, tp); //交换指针 用tmp存下上轮的rak rk[sa[1]] = p = 1; //用sa更新rak并离散 编号从1开始第一个定为1 for (i = 2; i <= n; i++) { if (tp[sa[i]] != tp[sa[i - 1]] || tp[sa[i] + l] != tp[sa[i - 1] + l]) //压缩 相同子串记为同一编号 p++; rk[sa[i]] = p; //rak与sa互逆 } } } void get_height() //heig[i]为str[sa[i-1]]与str[sa[i]]的最长公共前缀 { for (int i = 1; i <= n; i++) //由于rak计算过程中是用指针 函数退出后不确定最后存在哪个数组重新计算 rak[sa[i]] = i; int k = 0; for (int i = 1; i <= n; i++) { if (k) //heig[i] >= heig[i - 1] - 1 k--; int j = sa[rak[i] - 1]; //以i-1为开头的串排序的前一位 while (a[i - 1 + k] == a[j - 1 + k]) //字符串0~n-1 k++; heig[rak[i]] = k; //存在i位置 有效值2~n } } int main() { #ifdef LOCAL freopen("C:/input.txt", "r", stdin); #endif int K; cin >> n >> K; for (int i = 0; i < n; i++) scanf("%d", &a[i]); suffix(a); get_height(); multiset<int> st; for (int i = 2; i < K; i++) //滑动区间最值 st.insert(heig[i]); int ans = 0; for (int i = K; i <= n; i++) { if (i - K + 1 >= 2) st.erase(st.find(heig[i - K + 1])); st.insert(heig[i]); ans = max(ans, *st.begin()); } cout << ans << endl; return 0; }