KUPC2016 : G - 試験 / Exam

これは解けて良かった。
http://kupc2016.contest.atcoder.jp/tasks/kupc2016_g

問題

文字列Tが与えられる。
Tに対する文字列の集合Sは以下の条件を満たす物とする。

• Sの各要素はTの連続する部分文字列である。
• Sの2要素x,yを取ったとき、片方が片方の部分文字列であるということがない。

条件を満たすSの最大文字数を求めよ。

解法

SuffixArray + 累積和で解く。
Tのうち互いに一致しない同じ長さの部分文字列を幾つか選んでSを構築することを考える。
TのSAを求める過程で2つのsuffixのLCPが求められるので、このLCPより長い(Suffixの)prefixをSの要素として取れば、条件を満たすSの要素が1個増える。
そのような取り得るprefixの長さの登場回数を、累積和を取って求め、登場回数が最大となるprefix長を求めよう。

int N;
string T;
int S[202020];

struct SuffixArray {
	int N; vector<int> rank,lcp,sa; string S;
	
	SuffixArray(string S) : S(S){
		int i,h=0; vector<int> tmp,tr;
		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); tr.resize(N+1);
		FOR(i,N+1) tr[sa[i]]=i;
		FOR(i,N) {
			int j=sa[tr[i]-1];
			for(h=max(h-1,0);i+h<N && j+h<N; h++) if(S[j+h]!=S[i+h]) break;
			lcp[tr[i]-1]=h;
		}
	}
};


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	N=T.size();
	
	SuffixArray sa(T);
	FOR(i,N) {
		S[sa.lcp[sa.rank[i]-1]+1]++;
		S[N-i+1]--;
	}
	
	int ma=0;
	for(i=1;i<=N;i++) {
		S[i]+=S[i-1];
		ma=max(ma,S[i]);
	}
	cout<<ma<<endl;
}

まとめ

SA未だに使い慣れない。