#include using namespace std; const int INF = 1 << 30; int main() { int dp[1201][1201]; pair< int, int > pos[1201][1201]; fill_n(*dp, 1201 * 1201, INF); fill_n(*pos, 1201 * 1201, make_pair(-1, -1)); int poyo[1201] = {}; int piyo[1201] = {}; int n, m; string S, T; cin >> n >> m; cin >> S; cin >> T; for(int i = 0; i <= T.size(); i++) { dp[0][i] = (i == 0 ? 0 : 9 + 2 * (i - 1)); if(i != 0) pos[0][i] = {0, 0}; } for(int i = 0; i <= S.size(); i++) { dp[i][0] = (i == 0 ? 0 : 9 + 2 * (i - 1)); if(i != 0) pos[i][0] = {0, 0}; } for(int i = 0; i < S.size(); i++) { for(int j = 0; j < T.size(); j++) { int val = S[i] == T[j] ? dp[i][j] : dp[i][j] + 5; pair< int, int > rev = {i, j}; int val2 = INF; pair< int, int > rev2 = {i, j}; for(int k = poyo[i]; k <= j; k++) { int cost = dp[i + 1][k] + 9 + 2 * (j - k); if(cost < val2) { val2 = cost; rev2 = {i + 1, k}; poyo[i] = k; } } if(val2 < val) { val = val2; rev = rev2; } val2 = INF; rev2 = {i, j}; for(int k = piyo[j]; k <= i; k++) { int cost = dp[k][j + 1] + 9 + 2 * (i - k); if(cost < val2) { val2 = cost; rev2 = {k, j + 1}; piyo[j] = k; } } if(val2 < val) { val = val2; rev = rev2; } dp[i + 1][j + 1] = min(dp[i + 1][j + 1], val); pos[i + 1][j + 1] = rev; } } cout << dp[S.size()][T.size()] << endl; pair< int, int > now = {S.size(), T.size()}; string AA = "", BB = ""; while(pos[now.first][now.second].first != -1) { auto qq = pos[now.first][now.second]; if(qq.first + 1 == now.first && qq.second + 1 == now.second) { AA += S[qq.first]; BB += T[qq.second]; } else if(qq.first == now.first) { for(int j = 0; j < now.second - qq.second; j++) AA += "-"; for(int j = 0; j < now.second - qq.second; j++) BB += T[now.second - j - 1]; } else { for(int j = 0; j < now.first - qq.first; j++) BB += "-"; for(int j = 0; j < now.first - qq.first; j++) AA += S[now.first - j - 1]; } now = qq; } reverse(begin(AA), end(AA)); reverse(begin(BB), end(BB)); cout << AA << endl; cout << BB << endl; }