Typical DP Contest G - 辞書順

問題

文字列sが与えられる。
sの（必ずしも連続しない）部分文字列でK番目のものを求めよ。
部分文字列は、文字列が同じならどこから切り出したかは区別しない。
K番目が存在しない場合はEelと出力せよ。

制約条件

sは英小文字からなる
sの長さ≦10^6

方針

まずsのユニークな部分文字列の個数を数える。
dp[i]をi文字目を使い、i文字目以降のユニークな部分文字列の個数とする。

dp[i]は次の'a'〜次の'z'の位置をpos1〜pos26とすれば、
dp[i] = 1+Σ{dp[pos_j] | 1 ≦ j ≦ 26}と書ける。
（ユニークな文字列の個数を数えたいので、aが二つあったら、最初のaを飛ばして二個目以降のaを使うのを禁止すればよい。すなわち、同じ文字は最初のもののみを使えるようにすれば、重複なしで数えられる）

したがって、iを後ろからまわして、現在のところのΣa〜zの個数 = totをもっておき、
dp[i]を求めたら、totから前回の同じ文字のdp[j]を引いて、かわりにdp[i]を足して……としていけばよい。
（日本語が怪しいのでソース参照）

で、個数が数えられたら、先頭から使う文字を1文字ずつ決めていけばよい。
dpテーブルでn番目を復元する典型通り、個数がKを超えたところでその文字を使う、としていく。

ソースコード

string s;
int n, next[1000010][26];
ll K, dp[1000010], prev[26];
 
int main(){
	cin >> s >> K;
	n = s.size();
	memset(next, -1, sizeof(next));
	
	for(int i = n - 1; i >= 0; i--) rep(j, 26){
		next[i][j] = s[i] - 'a' == j ? i : next[i+1][j];
	}
	
	ll tot = 1;
	dp[n] = 1;
	for(int i = n - 1; i >= 0; i--){
		int c = s[i] - 'a';
		dp[i] = tot;
		tot += dp[i] - min(prev[c], inf);
		tot = min(tot, 2 * inf);
		prev[c] = dp[i];
	}
	
	K = min(K, tot);
	
	string ans;
	int pos = -1;
	
	while(K > 0){
		int i = 0;
		for(; i < 26; i++){
			int np = next[pos+1][i];
			if(np < 0) continue;
			if(dp[np] >= K){
				ans += 'a' + i;
				pos = np;
				K--;
				break;
			}
			K -= dp[np];
		}
		if(i >= 26){
			break;
		}
	}
	if(ans == "") ans = "Eel";
	cout << ans << endl;
	
	return 0;
}