#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define input_init stringstream ss; string strtoken, token; istringstream is #define input_line getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit) #define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num int dp[1001][1001]; int ii[1001][1001]; int jj[1001][1001]; int main(void){ int n,m; string s; string t; cin >> n>>m >> s >> t; for (int i = 0; i < 1001; i++) for (int j = 0; j < 1001; j++) ii[i][j] = -1; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (s[i] == t[j]){ dp[i + 1][j + 1] = dp[i][j] + 1; ii[i + 1][j + 1] = i; jj[i + 1][j + 1] = j; } else{ if (dp[i + 1][j] > dp[i][j + 1]){ dp[i + 1][j + 1] = dp[i + 1][j]; ii[i + 1][j + 1] = ii[i+1][j]; jj[i + 1][j + 1] = jj[i+1][j]; } else{ dp[i + 1][j + 1] = dp[i][j+1]; ii[i + 1][j + 1] = ii[i][j+1]; jj[i + 1][j + 1] = jj[i][j+1]; } } } } string com; int x=n, y=m; while (ii[x][y] >= 0){ com = s[ii[x][y]]+com; int t = x; x = ii[t][y]; y = jj[t][y]; } //cout << com << endl; int len = (int)com.size(); int res = 0; int nn = 0; for (int i = 0; i < m; i++){ //cout << s << " " << t << " " << i <<" "<= len){ res++; } else if (com[nn] == s[i] && com[nn] == t[i])nn++; else if (s[i] == t[i])continue; else if (com[nn] == s[i]){ s.insert(i, t.substr(i, 1)); res++; } else if (com[nn] == t[i]){ s.erase(i, 1); i--; res++; } else{ s[i] = t[i]; res++; } } cout << res << endl; return(0); }