#include #include #include #include using namespace std; const int inf = 1012345678; int main() { cin.tie(0); ios_base::sync_with_stdio(false); int N, M; string S, T; cin >> N >> M >> S >> T; vector > > dp(N + 1, vector >(M + 1, vector(3, inf))); dp[0][0][0] = 0; for (int i = 0; i <= N; ++i) { for (int j = 0; j <= M; ++j) { if (i >= 1 && j >= 1) { dp[i][j][0] = min({ dp[i - 1][j - 1][0], dp[i - 1][j - 1][1], dp[i - 1][j - 1][2] }) + (S[i - 1] == T[j - 1] ? 0 : 5); } if (i >= 1) { dp[i][j][1] = min({ dp[i - 1][j][0] + 9, dp[i - 1][j][1] + 2, dp[i - 1][j][2] + 9 }); } if (j >= 1) { dp[i][j][2] = min({ dp[i][j - 1][0] + 9, dp[i][j - 1][1] + 9, dp[i][j - 1][2] + 2 }); } } } int res = min({ dp[N][M][0], dp[N][M][1], dp[N][M][2] }); int cx = N, cy = M, cz = (res == dp[N][M][0] ? 0 : (res == dp[N][M][1] ? 1 : 2)); string SA, TA; while (cx != 0 || cy != 0) { int cur = dp[cx][cy][cz]; if (cx >= 1 && cy >= 1) { int tar = cur - (S[cx - 1] == T[cy - 1] ? 0 : 5); bool f = false; if (dp[cx - 1][cy - 1][0] == tar) cz = 0, f = true; else if (dp[cx - 1][cy - 1][1] == tar) cz = 1, f = true; else if (dp[cx - 1][cy - 1][2] == tar) cz = 2, f = true; if (f) { SA += S[--cx]; TA += T[--cy]; continue; } } if (cx >= 1) { bool f = false; if (dp[cx - 1][cy][0] == cur - 9) cz = 0, f = true; else if (dp[cx - 1][cy][1] == cur - 2) cz = 1, f = true; else if (dp[cx - 1][cy][2] == cur - 9) cz = 2, f = true; if (f) { SA += S[--cx]; TA += "-"; continue; } } if (cy >= 1) { bool f = false; if (dp[cx][cy - 1][0] == cur - 9) cz = 0, f = true; else if (dp[cx][cy - 1][1] == cur - 9) cz = 1, f = true; else if (dp[cx][cy - 1][2] == cur - 2) cz = 2, f = true; if (f) { SA += "-"; TA += T[--cy]; continue; } } } reverse(SA.begin(), SA.end()); reverse(TA.begin(), TA.end()); cout << res << endl; cout << SA << endl; cout << TA << endl; return 0; }