Suffix Automaton

Suffix Automaton.cpp

#ifndef SUFFIX_AUTOMATON
#define SUFFIX_AUTOMATON
#include<vector>
template<char L='a',char R='z'>
struct suffix_automaton{
	struct node{
		int ch[R-L+1],fa,len;
		node(int l=0):fa(0),len(l){
			for(int i=0;i<=R-L;++i)ch[i]=0;
		}
	};
	std::vector<node >S;
	int tail,u,v,np,vp;
	suffix_automaton():S(2),tail(1){S[0].fa=0;}
	inline void add(int c){
		c-=L;
		u=tail;
		S.push_back(node(S[u].len+1));
		tail=np=S.size()-1;
		for(;u&&!S[u].ch[c];u=S[u].fa)S[u].ch[c]=np;
		if(!u)S[np].fa=1;
		else{
			v=S[u].ch[c];
			if(S[v].len==S[u].len+1)S[np].fa=v;
			else{
				S.push_back(S[v]);
				vp=S.size()-1;
				S[vp].len=S[u].len+1;
				S[v].fa=S[np].fa=vp;
				for(;u&&S[u].ch[c]==v;u=S[u].fa)S[u].ch[c]=vp;
			}
		}
	}
	inline int size(){return S.size()-2;}
};
#endif