Codeforces 176 D. Hyper String

問題

n個の文字列b1, ..., bnが与えられる。
m個のインデックスi1, ..., imが与えられる。
文字列tを、bi1 + bi2 + ... + bimとする。(ただし+は文字列の結合をあらわす)


別の文字列sが与えられる。
このとき、sとtの最長共通部分列(連続しなくともよい)の長さを求めよ。

制約条件

文字列は全て英小文字からなる。
bの文字列の長さを全て足した和は10^6以下

n, m≦2000
tの長さ≦2000

方針

最長共通部分列だけど、sの長さが凄く長い。
だけど、アルファベットというのは26字しかないから、sに前処理ができて、O(|t|^2)時間のDPで最長共通部分列が求まるよという感じ。


dp[i][j]を、tのi文字目までがsにj文字マッチしたときの、sの位置の最小値とする。
これを更新するようなDPは、sの位置において、その文字が次に現れる位置がわかっていれば、O(|t|^2)で出来て、
その文字が次に現れる位置というのは後ろから見てインデックスを更新していけば、O(|b| * 26)できる。


jのループの向きを逆にすると配列が一次元で済む。
別に二次元でやっても余裕なのであれだけど。

ソースコード

int n, m, ord[2000], len;
string s[2000], t;

int nexts[2001][26];
vi next[2000][26];
pi dp[2001];

void run()
{
	cin >> n;
	rep(i, n) cin >> s[i];
	cin >> m;
	rep(i, m) cin >> ord[i], ord[i]--;
	cin >> t;
	len = t.size();
	
	rep(i, n){
		rep(j, 26){
			next[i][j] = vi(s[i].size() + 1, s[i].size());
			for(int k = (int)s[i].size() - 1; k >= 0; k--){
				if(s[i][k] - 'a' == j) next[i][j][k] = k;
				else next[i][j][k] = next[i][j][k + 1];
			}
		}
	}
	rep(i, 26){
		nexts[m][i] = m;
		for(int j = m - 1; j >= 0; j--){
			if(next[ord[j]][i][0] < s[ord[j]].size()) nexts[j][i] = j;
			else nexts[j][i] = nexts[j + 1][i];
		}
	}
	
	rep(i, len + 1) dp[i] = mp(i ? m : 0, 0);
	int ans = 0;
	
	rep(i, len) for(int j = i; j >= 0; j--) if(dp[j].first < m){
		int a = dp[j].first, b = dp[j].second, c = t[i] - 'a';
		
		if(next[ord[a]][c][b] < s[ord[a]].size()){
			dp[j+1] = min(dp[j+1], mp(a, next[ord[a]][c][b] + 1));
			ans = max(ans, j+1);
		}
		else if(nexts[a+1][c] < m){
			int na = nexts[a+1][c];
			dp[j+1] = min(dp[j+1], mp(na, next[ord[na]][c][0] + 1));
			ans = max(ans, j+1);
		}
	}
	cout << ans << endl;
}