LIS(最長共通部分列)
#LIS
DP
まずはコードを
code:cpp
ll dp
2005
2005
;
void _main(){
STR(s,t);
ll m = s.length(),n = t.length();
rep(i,0,m){
rep(j,0,n){
if(s
i
==t
j
)dp
i+1
j+1
=dp
i
j
+1;
else dp
i+1
j+1
=max(dp
i
j+1
,dp
i+1
j
);
}
}
cout<<dp
m
n
<<endl;
}
特に言うことなし。計算量は2つの文字列の長さの積になる。