CSAcademy Round #73 : E. Strange Substring

苦手なタイプの問題だけど解けて良かった。
https://csacademy.com/contest/round-73/task/strange-substring/

問題

２つの文字列A,Bが与えられる。
AのsubstringでありBのsubstringとはならない文字列について、uniqueなものはいくつあるか。

解法

Suffix Automatonを使うと簡単らしいが、自分はそのテクを知らないのでSuffix Arrayを使う

uniqueな部分文字列の数を数え上げる場合、Suffix Arrayを使うことが考えられる。
S=A+"#"+Bという文字列を考え、Suffix Arrayを構築しよう。

このSuffix Arrayにおいて、対応する開始位置がA内の場合、他に開始位置がB内の物に対するLCPの最大値がPだとすると、AのSubstringのうち、長さがP+1以上のものを取ればBのSubstringになりえない。
よってSuffix Arrayを構築後、各開始位置に対しP+1以上の長さのSubstringの数を数え上げよう。

struct SuffixArray {
	int N; vector<int> rank,lcp,sa,rsa; string S;
	
	SuffixArray(string S) : S(S){
		int i,h=0; vector<int> tmp;
		N=S.size(); rank.resize(N+1); sa.resize(N+1); tmp.resize(N+1);
		FOR(i,N+1) sa[i]=i, rank[i]=i==N?-1:S[i];
		
		for(int k=1; k<=N; k<<=1) {
			auto pred2 = [k,this](int& a,int &b)->bool{ return (((a+k<=N)?rank[a+k]:-1)<((b+k<=N)?rank[b+k]:-1));};
			auto pred = [pred2,k,this](int& a,int &b)->bool{ return (rank[a]!=rank[b])?(rank[a]<rank[b]):pred2(a,b);};
			int x=0;
			if(k!=1) for(i=1;i<N+1;i++) if(rank[sa[i]]!=rank[sa[x]]) sort(sa.begin()+x,sa.begin()+i,pred2), x=i;
			sort(sa.begin()+x,sa.end(),pred);
			FOR(i,N+1) tmp[sa[i]]=(i==0)?0:tmp[sa[i-1]]+pred(sa[i-1],sa[i]);
			swap(rank,tmp);
		}
		lcp.resize(N+1); rsa.resize(N+1);
		FOR(i,N+1) rsa[sa[i]]=i;
		FOR(i,N) {
			int j=sa[rsa[i]-1];
			for(h=max(h-1,0);i+h<N && j+h<N; h++) if(S[j+h]!=S[i+h]) break;
			lcp[rsa[i]-1]=h;
		}
	}
};

string A,B,S;
int NA,NB;
int sameb[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	NA=A.size();
	NB=B.size();
	S=A+"#"+B;
	
	SuffixArray SA(S);
	ll ret=0;
	
	int pre=0;
	for(i=1;i<=NA+NB+1;i++) {
		if(SA.sa[i]>NA) {
			pre=S.size()-SA.sa[i];
		}
		else {
			pre=min(pre,SA.lcp[i-1]);
			sameb[i]=max(pre,SA.lcp[i-1]);
		}
	}
	pre=0;
	for(i=NA+NB+1;i>=1;i--) {
		if(SA.sa[i]>NA) {
			pre=S.size()-SA.sa[i];
		}
		else {
			pre=min(pre,SA.lcp[i]);
			sameb[i]=max(sameb[i],pre);
			ret+=NA-SA.sa[i]-sameb[i];
		}
	}
	
	cout<<ret<<endl;
	
}

まとめ

Suffixなんとか系苦手。