后缀自动机SAM 学习笔记

upd:学会后缀树了，所以这东西就扔了

不是很理解

struct deme{int len,fa,to[26];}dot[m7];
void insert(int ch){
	cnt++;
	int p=las,np=cnt;las=np;
	num[np]=1;
	dot[np].len=dot[p].len+1;
	
	while(p&&!dot[p].to[ch])dot[p].to[ch]=np,p=dot[p].fa;
	if(!p){dot[np].fa=1;return;}
	
	int q=dot[p].to[ch];
	if(dot[q].len==dot[p].len+1){dot[np].fa=q;return;}
	
	cnt++;int nq=cnt;
	dot[nq]=dot[q];
	dot[nq].len=dot[p].len+1,dot[q].fa=dot[np].fa=nq;
	while(p&&dot[p].to[ch]==q)dot[p].to[ch]=nq,p=dot[p].fa;
}