题目链接
解析
后缀自动机+线段树
若一个子串可识别，那么它的\(right\)集合大小一定为\(1\)
对于一个\(right\)大小为\(1\)的节点：
它的\(right\)仅包含\(maxlen\)
对\([1,minlen]\)的每一个位置\(x\)产生\(maxlen - x + 1\)的贡献，因为\(str[x..maxlen]\)只在\(maxlen\)处出现，是一个可识别子串
对\([minlen - 1, maxlen]\)的每个位置\(x\)产生\(minlen\)的贡献，因为\(str[x..maxlen]\)必定在其它位置出现，不是可识别子串，包含该位置的最短可识别子串为\(str[maxlen - minlen + 1..maxlen]\)
两种贡献分别建线段树统计每个位置的最小值即可
代码
P.S.字符串长度先处理出来，否则像我开始一样T得飞起。。。。
#include#include #include #include #define MAXN 100005typedef long long LL;struct SuffixAutomaton { struct Node { Node *next[26], *link; int maxlen, once; void friend cpy(Node *a, const Node *b) { a->maxlen = b->maxlen, a->once = b->once, a->link = b->link; for (int i = 0; i < 26; ++i) a->next[i] = b->next[i]; } } * root, *last, *node[MAXN << 1]; int cnt; SuffixAutomaton() { last = root = new Node(); } void build(char *); Node *add(char); void work();} sam;struct SegmentTree { int tree[MAXN << 4], upd[MAXN << 4]; SegmentTree() { memset(tree, 0x3f, sizeof tree); memset(upd, 0x3f, sizeof upd); } void push_down(int); void update(int, int, int, int, int, int); int query(int, int, int, int);} tree1, tree2;char string[MAXN];int N;int main() { std::ios::sync_with_stdio(false); std::cin >> (string + 1); N = strlen(string + 1); sam.build(string); sam.work(); for (int i = 1; i <= N; ++i) std::cout << std::min(tree1.query(1, 1, MAXN, i) - i, tree2.query(1, 1, MAXN, i)) << std::endl; return 0;}void SuffixAutomaton::build(char *str) { for (int i = 1; i <= N; ++i) last = add(str[i]);}SuffixAutomaton::Node *SuffixAutomaton::add(char ch) { int c = ch - 'a'; Node *np = new Node(), *p = last; node[++cnt] = np; np->maxlen = p->maxlen + 1, np->once = 1; while (p && !p->next[c]) p->next[c] = np, p = p->link; if (!p) np->link = root; else { Node *q = p->next[c]; if (p->maxlen + 1 == q->maxlen) np->link = q; else { Node *nq = new Node(); node[++cnt] = nq; cpy(nq, q); nq->maxlen = p->maxlen + 1; q->link = np->link = nq; while (p && p->next[c] == q) p->next[c] = nq, p = p->link; } } return np;}void SuffixAutomaton::work() { for (int i = 1; i <= cnt; ++i) node[i]->link->once = 0; for (int i = 1; i <= cnt; ++i) if (node[i]->once) { SuffixAutomaton::Node *p = node[i]; tree1.update(1, 1, MAXN, 1, p->maxlen - p->link->maxlen, p->maxlen + 1); tree2.update(1, 1, MAXN, p->maxlen - p->link->maxlen, p->maxlen, p->link->maxlen + 1); }}void SegmentTree::push_down(int id) { if (upd[id] ^ 0x3f3f3f3f) { upd[id << 1] = std::min(upd[id << 1], upd[id]); upd[id << 1 | 1] = std::min(upd[id << 1 | 1], upd[id]); tree[id << 1] = std::min(tree[id << 1], upd[id]); tree[id << 1 | 1] = std::min(tree[id << 1 | 1], upd[id]); upd[id] = 0x3f3f3f3f; }}void SegmentTree::update(int id, int L, int R, int l, int r, int v) { if (L >= l && R <= r) tree[id] = std::min(tree[id], v), upd[id] = std::min(upd[id], v); else { int mid = (L + R) >> 1; if (l <= mid) update(id << 1, L, mid, l, r, v); if (r > mid) update(id << 1 | 1, mid + 1, R, l, r, v); }}int SegmentTree::query(int id, int L, int R, int p) { if (L == R) return tree[id]; push_down(id); int mid = (L + R) >> 1; if (p <= mid) return query(id << 1, L, mid, p); else return query(id << 1 | 1, mid + 1, R, p);}//Rhein_E