Description：

对于每一个位置 $x$ ，统计 $x\in[l,r]$ ，并且 $S[l,r]$ 在 $S$ 中只出现一次的最短的 $S[l,r]$ 。

$1\leqslant n\leqslant 10^5$

Solution：

比较简单的一道题，只出现过一次那么 $|Right|$ 就是 $1$ ，那么只要把所有这样的点找出来，设他的位置是 $p$ ，这个可以在建自动机的时候求出，那么 $i\in [1,s[i].maxl-s[s[i].par].maxl]$ 可以用 $r-i+1$ 更新，不要忘了 $i\in[s[i].maxl-s[s[i].par].maxl + 1,s[i].maxl]$ 还可以用 $r-l+1$ 更新，第一个更新最后再考虑 $i$ 那么开两棵线段树就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 100010

char c[MAXN];

struct node

{

	int par,maxl;

	int tr[26];

}s[MAXN << 1];

int root = 1,last = 1,ptr = 1;

int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

void extend(int k)

{

	int p = last;

	int np = newnode(s[p].maxl + 1);

	for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

	if(p == 0)s[np].par = root;

	else

	{

		int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

		else

		{

			int nq = newnode(s[p].maxl + 1);

			memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

			s[nq].par = s[q].par;

			s[q].par = s[np].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

		}

	}

	last = np;

	return;

}

int ind[MAXN];

int ans[MAXN];

int val[MAXN];

struct SEG

{

	struct node

	{

		int lc,rc;

		int val;

	}t[MAXN << 1];

	int ptr;

	int newnode(){return ++ptr;}

	int root;

	SEG(){ptr = 0;}

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		t[rt].val = 0x3f3f3f3f;

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void add(int rt,int L,int R,int k,int l,int r)

	{

		if(k > t[rt].val)return;

		if(L <= l && r <= R)

		{

			t[rt].val = k;

			return;

		}

		if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

		if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

		return;

	}

	void update(int rt,int l,int r)

	{

		if(l == r)

		{

			val[l] = t[rt].val;

			return;

		}

		t[t[rt].lc].val = min(t[t[rt].lc].val,t[rt].val);

		t[t[rt].rc].val = min(t[t[rt].rc].val,t[rt].val);

		update(t[rt].lc,l,mid);

		update(t[rt].rc,mid + 1,r);

		return;

	}

}t1,t2;

int main()

{

	scanf("%s",c + 1);

	int l = strlen(c + 1);

	for(int i = 1;i <= l;++i)extend(c[i] - 'a');

	for(int i = 2;i <= ptr;++i)++ind[s[i].par];

	t1.build(t1.root,1,l);t2.build(t2.root,1,l);

	for(int i = 1;i <= ptr;++i)

	{

		if(ind[i] != 0)continue;

		int r = s[i].maxl - s[s[i].par].maxl;

		t1.add(t1.root,1,r,s[i].maxl + 1,1,l);

		t2.add(t2.root,r + 1,s[i].maxl,s[s[i].par].maxl + 1,1,l);

	}

	memset(ans,0x3f,sizeof(ans));

	t1.update(t1.root,1,l);

	for(int i = 1;i <= l;++i)ans[i] = min(ans[i],val[i] - i);

	t2.update(t2.root,1,l);

	for(int i = 1;i <= l;++i)ans[i] = min(ans[i],val[i]);

	for(int i = 1;i <= l;++i)printf("%d\n",ans[i]);

	return 0;

}