SRM 298 DIV1 Hard CountingCommonSubsequences

問題 Editorial

問題

ある文字列のサブシークエンスとは、その文字列から任意の個数の文字を消したものである(連続している必要はない)。
3つの文字列a,b,cが与えられる。この3つの文字列に共通する空でないサブシークエンスの数(同じ文字列は重複して数えない)を求めよ

• 1 <= |a|, |b|, |c| <= 50

解答

(aのインデックス * bのインデックス * cのインデックス)でDP。
重複を省くために、文字列を作る方向で考える。
各状態で次の文字を全て試し、a,b,cのそれぞれその文字である次の最小のインデックスの所へ進む感じ。
次の文字の位置を別のDPで計算すれば計算量は落ちるが、毎回検索しても十分間に合う

コメント

重複を省くために「文字列を作る」方向で考えるというのは極めて基本的であって、普通に高速に思い浮かんでできなければならないな

コード

#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;

typedef long long ll;   

ll dp[55][55][55];
int nexttable[3][26][55];
struct CountingCommonSubsequences {
	string s[3];
	ll rec(int i0, int i1, int i2) {
		if(dp[i0][i1][i2] != -1) return dp[i0][i1][i2];
		ll r = 1;	//empty
		rep(c, 26) {
			int j0 = nexttable[0][c][i0], j1 = nexttable[1][c][i1], j2 = nexttable[2][c][i2];
			if(j0 != INF && j1 != INF && j2 != INF)
				r += rec(j0+1, j1+1, j2+1);
		}
		return dp[i0][i1][i2] = r;
	}
	long long countCommonSubsequences(string a_, string b_, string c_) {
		s[0] = a_, s[1] = b_, s[2] = c_;
		mset(nexttable, INF);
		rep(si, 3) {
			string t = s[si];
			rep(c, 26)
				for(int i = t.size()-1; i >= 0; i --)
					nexttable[si][c][i] = t[i]-'a' == c ? i : nexttable[si][c][i+1];
		}
		mset(dp, -1);
		return rec(0, 0, 0) - 1;	//-1: "non empty"
	}
};