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; }
まとめ
意外とコードは短い。