Description：

给出一个长度为 $n$ 的字符串 $s[1]$ ，由小写字母组成。定义一个字符串序列 $s[1\dots k]$ ，满足性质： $s[i]$ 在 $s[i-1]$ $(i\geqslant 2)$ 中出现至少两次（位置可重叠），问最大的 $k$ 是多少，使得从 $s[1]$ 开始到 $s[k]$ 都满足这样一个性质。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

首先这道题的主体思路是先把这个串的后缀自动机建出来，然后沿着 $parent$ 树从上往下递推，因为 $parent$ 树的父亲一定是儿子的后缀，所以只要确定父亲在儿子中除了后缀那一次是否还出现过另外一次即可，之所以一定是后缀是因为如果 $A$ 在 $B$ 中出现了两次以上，那么把最左边的 $A$ 左边的和最右边的 $B$ 右边的都删掉得到 $B'$ ， $B'$ 还是满足条件的，但是比 $B$ 更容易成为别的的子串，现在唯一的问题就变成了如何判断后缀自动机某个位置代表的串是不是在他儿子的串中出现，我们把这两个状态的 $right$ 集合求出来，那么在儿子 $right$ 集合中随便选一个 $pos$ ， $[pos-maxl[p]+maxl[fa],pos]$ 这个区间中一定有父亲的 $right$ 集合中的元素，因为任意一个儿子都包含父亲，于是我们可以给每个点开一个线段树维护 $right$ 集合，上面那个过程就是查询区间中是否有元素，在构造的时候依次向上线段树合并，因为父亲的 $right$ 集合是儿子的并集，如果有元素，就 $+1$ ，否则把父亲的继承下来，注意还要维护一个 $top$ 表示由于继承了父亲的所以实际这个点所代表的串已经改变了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 400010

char str[MAXN];

namespace SAM

{

	struct node

	{

		int par,maxl,pos;

		int tr[26];

	}s[MAXN];

	int cur = 1,root = 1,last = 1;

	int newnode(int x){int k = ++cur;s[k].maxl = x;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);

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

				memcpy(s[nq].tr,s[q].tr,sizeof(s[nq].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 c[MAXN],p[MAXN];

}

namespace Tree

{

	struct node

	{

		int lc,rc;

	}t[MAXN * 25];

	int ptr = 0;

	int root[MAXN];

	int newnode(){return ++ptr;}

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

	void insert(int &rt,int p,int l,int r)

	{

		int k = newnode();t[k] = t[rt];rt = k;

		if(l == r)return;

		if(p <= mid)insert(t[rt].lc,p,l,mid);

		else insert(t[rt].rc,p,mid + 1,r);

		return;

	}

	int merge(int x,int y)

	{

		if(x == 0 || y == 0)return x + y;

		int z = newnode();

		t[z].lc = merge(t[x].lc,t[y].lc);

		t[z].rc = merge(t[x].rc,t[y].rc);

		return z;

	}

	int query(int rt,int L,int R,int l,int r)

	{

		if(rt == 0)return 0;

		if(L <= l && r <= R)return 1;

		int res = 0;

		if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

		if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);

		return res;

	}

}

int f[MAXN],top[MAXN];

int main()

{

	scanf("%d",&n);

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

	using namespace SAM;

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

	{

		extend(str[i] - 'a');

		Tree::insert(Tree::root[last],i,1,n);

		s[last].pos = i;

	}

	for(int i = 1;i <= cur;++i)++c[s[i].maxl];

	for(int i = 1;i <= n;++i)c[i] += c[i - 1];

	for(int i = 1;i <= cur;++i)p[c[s[i].maxl]--] = i;

	for(int i = cur;i > 1;--i)

	{

		int fa = s[p[i]].par;

		Tree::root[fa] = Tree::merge(Tree::root[fa],Tree::root[p[i]]);

	}

	int ans = 1;

	for(int i = 2;i <= cur;++i)

	{

		int fa = s[p[i]].par;

		if(fa == 1)

		{

			f[p[i]] = 1;

			top[p[i]] = p[i];

			continue;

		}

		if(Tree::query(Tree::root[top[fa]],s[p[i]].pos - s[p[i]].maxl + s[top[fa]].maxl,s[p[i]].pos - 1,1,n))

		{

			f[p[i]] = f[fa] + 1;

			top[p[i]] = p[i];

		} 

		else

		{

			f[p[i]] = f[fa];

			top[p[i]] = top[fa];

		}

		ans = max(ans,f[p[i]]);

	}

	cout << ans << endl;

	return 0;

}