AtCoder ABC #130 : E - Common Subsequence

LCS2連発？
https://atcoder.jp/contests/abc130/tasks/abc130_e

問題

2つの文字列S,Tが与えられる。
S,Tの部分文字列の組のうち、等しいものは何通りか。
なお、抜き出した部分文字列が等しくても、抜き出した位置が異なるものは別々にカウントする。

解法

以下を考える。
dp(n,m) := 抜き出した等しい部分文字列のうち、末尾がS[n]、T[m]であるようなものの組み合わせ
dp(0,0)=1から初めて、順次dp(|S|,|T|)まで求めていこう。
dp(n,m)の総和が解となる。

• S[n]!=T[m]の時、dp(n,m)=0
• S[n]==T[m]の時、dp(n,m)=sum(dp(n',m')) (0≦n'＜n、0≦m'＜m)

後者はdpテーブルの二次元累積和を更新しながら処理すればO(1)で求まるので、このDPは全体でO(|S||T|)で済む。

int N,M;
int S[2020];
int T[2020];
ll num[2020][2020];
ll sum[2020][2020];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>S[i];
	FOR(i,M) cin>>T[i];
	
	FOR(x,2020) sum[x][0]=sum[0][x]=1;
	ll ret=1;
	FOR(x,N) FOR(y,M) {
		if(S[x]==T[y]) {
			num[x+1][y+1]=(sum[x][y])%mo;
			ret+=num[x+1][y+1];
		}
		sum[x+1][y+1]=(sum[x][y+1]+sum[x+1][y]+mo-sum[x][y]+num[x+1][y+1])%mo;
	}
	
	cout<<ret%mo<<endl;
	
}

まとめ

意外とコードは短い。