#include #define rep(i,a,b) for(int i=int(a);i> N >> M; string S,T,R; cin >> S >> T; int dp[N+1][M+1] = {}, table[N+1][M+1] = {};//↖↑←123 rep(i,1,N+1)rep(j,1,M+1){ if(i == 0 || j == 0)dp[i][j] = 0; else if(S[i-1] == T[j-1]){ dp[i][j] = dp[i-1][j-1] + 1; table[i][j] = 1; }else{ dp[i][j] = max(dp[i-1][j], dp[i][j-1]); if(dp[i-1][j] > dp[i][j-1])table[i][j] = 2; else table[i][j] = 3; } } //cout << dp[N][M] << endl; for(int i = N,j = M;table[i][j] != 0;){ if(table[i][j] == 1){ R = S[i-1] + R; i--,j--; }else if(table[i][j] == 2)i--; else j--; } //cout << R << endl; int cnt = 0; S += "0",T += "0",R += "0"; for(int i = 0,j = 0,k = 0;i < R.size();i++,j++,k++){ int d1 = 0, d2 = 0; while(R[i] != S[j]){j++;d1++;} while(R[i] != T[k]){k++;d2++;} cnt += max(d1, d2); } cout << cnt << endl; //cout << max(N,M) - R.size() + 1 << endl; }