Application Page

最短唯一子数组题解

这一页才使用那道题：为什么“最短唯一子数组”可以被翻译成“某个后缀需要比左右邻居多看一位”。

解题流程

间隔毫秒

为什么

后缀排序

答案

每个起点的 need

起点	left	right	same	need	状态

C++

核心代码

这段只展示题目应用层：compress、buildSuffixArray、buildLCP 的基础知识分别在两本基础页里讲。

int smallestUniqueSubarray(vector<int>& a) {    int n = a.size();    a = compress(a);    auto sa = buildSuffixArray(a);    auto lcp = buildLCP(a, sa);     vector<int> rank(n);    for (int i = 0; i < n; i++) rank[sa[i]] = i;     int res = n;    for (int i = 0; i < n; i++) {        int p = rank[i];        int same = 0;        if (p > 0) same = max(same, lcp[p]);        if (p + 1 < n) same = max(same, lcp[p + 1]);        int need = same + 1;        if (need <= n - i) res = min(res, need);    }    return res;}