【gym_102878E】Eigen Substring（后缀自动机）

https://codeforces.com/gym/102878/problem/E

题目描述

如果字符串$s$的子串$s[l..r]$在$s$中只出现一次，那么称它为$s$的特征子串。

给定字符串$s$，询问它的每个前缀的最短特征子串的长度。

输入格式

共两行。
第一行一个整数$n(1\le n\le 10^6)$，表示$s$的长度。
第二行一个字符串$s$，所有字符均为英文小写字母。

输出格式

共$n$行。
第$i$行一个整数，表示字符串$s[1..i]$的最短特征子串的长度。

输入样例

5
ababb

输出样例

1
1
1
2
2

思路

后缀自动机可以维护所有子串的出现次数。（具体操作是对每一个非复制状态，将其cnt赋值为1，否则为0，最后通过link树进行累计求和）

对于该题目，需要支持查询最小值、插入元素、删除元素操作，可以用multiset维护。

因此，每个非复制节点在新建时进行插入操作，被link后进行删除操作即可。

代码

#include<bits/stdc++.h>
#define rep(i, l, r) for(int i=l; i<=r; ++i)
#define N 1000006
using namespace std;
int n;
char s[N];
multiset<int> ms;
class SAM {	
	public:
		class state {
			public:
				int len; // length of longest string
				int link; // longest nonequivalent suffix
				int nxt[26]; // next states (default 0)
				bool vis;
		};
		state st[N*2]; // states
		int sz; // size
		int last; // last state
		
		void init() {
			last = 0;
			st[0].len = 0; // empty state
			st[0].link = -1;
			st[0].vis = false;
			sz = 1;
		}
		
		void extend(char c) {
			int cur = sz++; // new state
			st[cur].vis = false;
			st[cur].len = st[last].len + 1; // length
			int p = last;
			while(p != -1 && !st[p].nxt[c - 'a']) {
				st[p].nxt[c - 'a'] = cur;
				p = st[p].link;
			}
			if(p == -1) {
				st[cur].link = 0;
			} else {
				int q = st[p].nxt[c - 'a'];
				if(st[p].len + 1 == st[q].len) { // no other state
					st[cur].link = q;
					if(!st[q].vis){
						st[q].vis=true;
						ms.erase(ms.find(st[st[q].link].len+1));
					}
				} else {
					int clone = sz++;
					st[clone] = st[q];
					st[clone].len = st[p].len + 1;
					st[clone].vis = true;
					if(!st[q].vis) ms.erase(ms.find(st[st[q].link].len+1));
					while(p != -1 && st[p].nxt[c - 'a'] == q){
						st[p].nxt[c - 'a'] = clone; // transfer
						p = st[p].link;
					}
					st[q].link = st[cur].link = clone;
					if(!st[q].vis) ms.insert(st[st[q].link].len+1);
				}
			}
			last = cur;
			ms.insert(st[st[cur].link].len+1);
		}
};
SAM a;
int main() {
	scanf("%d%s", &n, s+1);
	a.init();
	rep(i, 1, n){
		a.extend(s[i]);
		printf("%d\n", *ms.begin());
	}
	return 0;
}