! SDOI2016生成魔咒

建立后缀自动机，题意为每次加入字符后求不同子串个数

新加入节点的贡献为\(maxlen(cur)-minlen(cur)+1=s[cur].len-s[s[cur].link].len\)

（从起点出发到当前点的路径数，若长度相同那么子串就相等的，所以是起点到当前点的不同串的长度数）

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=2e5+4;
long long ans;
namespace sam{
	struct samnode{
		map<int,int>nxt;
		bool cl;
		int link,len;
	}s[N<<1];
	int siz,las;
	inline void init(){
		siz=1;las=0;
		s[0].len=0;
		s[0].link=-1;
	}
	inline void extend(int c){
		int cur=siz++,p;
		s[cur].len=s[las].len+1;
		for(p=las;p!=-1&&!s[p].nxt[c];p=s[p].link)
			s[p].nxt[c]=cur;
		if(p==-1){s[cur].link=0;las=cur;}
		else{
			int q=s[p].nxt[c];
			if(s[q].len==s[p].len+1){s[cur].link=q;las=cur;}
			int clo=siz++;
			s[clo]=s[q];
			s[clo].cl=1;
			s[clo].len=s[p].len+1;
			for(;p!=-1&&s[p].nxt[c]==q;p=s[p].link)
				s[p].nxt[c]=clo;
			s[q].link=s[cur].link=clo;
			las=cur;
		}
		ans+=s[cur].len-s[s[cur].link].len;
	}
}
int main(){
	int n=read();
	sam::init();
	for(int i=1;i<=n;i++){
		sam::extend(read());
		cout<<ans<<"\n"; 
	} 
	return (0-0);
}

! SDOI2016生成魔咒

原文：https://www.cnblogs.com/aurora2004/p/12559702.html