TopCoder SRM 298 Div1 Hard CountingCommonSubsequences

問題

三つの文字列a,b,cが与えられる。
a,b,cの全てに（必ずしも連続しない）部分文字列として含まれる文字列はいくつあるか、求めよ。

制約条件

a,b,cはアルファベット小文字からなる。
a,b,cの長さ≦50

方針

動的計画法による。
dp[i][j][k]を、aをi文字目、bをj文字目、cをk文字目まで見たときの部分文字列の個数とする。
ここから、次の一文字を決めればDPテーブルが更新できる。

次の一文字は、aのi文字目以降、bのj文字目以降、cのk文字目以降の全てに含まれている必要がある。
その文字が複数あるときは、最初にでてきた文字だけを数えるようにすれば、漏れも重複もなく部分文字列を数え上げることができる。

ソースコード

int l1,l2,l3,n1[26][51], n2[26][51], n3[26][51];
ll dp[51][51][51];

struct CountingCommonSubsequences{
	ll countCommonSubsequences(string a,string b,string c){
		calc(n1,a); calc(n2,b); calc(n3,c);
		l1=a.size(); l2=b.size(); l3=c.size();
		dp[0][0][0]=1;
		ll ans=0;
		for(int i=0;i<l1;i++)for(int j=0;j<l2;j++)for(int k=0;k<l3;k++)if(dp[i][j][k]){
			for(int l=0;l<26;l++){
				int ni=n1[l][i], nj=n2[l][j], nk=n3[l][k];
				if(ni<0||nj<0||nk<0)continue;
				dp[ni+1][nj+1][nk+1]+=dp[i][j][k];
				ans+=dp[i][j][k];
			}
		}
		return ans;
	}
	void calc(int a[26][51],string s){
		int l=s.size();
		for(int i=0;i<26;i++)for(int j=0;j<l;j++){
			a[i][j]=-1;
			for(int k=j;k<l;k++)if(s[k]-'a'==i){
				a[i][j]=k; break;
			}
		}
	}
};