package N4xx; import java.util.Scanner; public class N422 { public static void main(String[] args) { new N422().solver(); } int N, M; String S, T; int[][][] dp; void solver() { Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); S = sc.next(); T = sc.next(); dp = new int[1300][1300][3]; for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[i].length; j++) { for (int k = 0; k < dp[i][j].length; k++) { dp[i][j][k] = -1; } } } System.out.println(dpdp(0, 0, 0)); dfs(0,0,0); System.out.println(RS + "\n" + RT); } String RS = ""; String RT = ""; int dpdp(int s, int t, int st) { if (s == N && t == M) return 0; int ret = dp[s][t][st]; if (ret != -1) return ret; ret = 10101010; if (s < N && t < M) ret = Math.min(ret, dpdp(s + 1, t + 1, 0) + ((S.charAt(s) == T.charAt(t) ? 0 : 5))); if (s < N) ret = Math.min(ret, ((st == 2) ? 2 : 9) + dpdp(s + 1, t, 2)); if (t < M) ret = Math.min(ret, ((st == 1) ? 2 : 9) + dpdp(s, t + 1, 1)); dp[s][t][st] = ret; return ret; } void dfs(int s, int t, int st) { if (s == N && t == M) return; int ret = dp[s][t][st]; if (s < N && t < M && ret == (dpdp(s + 1, t + 1, 0) + ((S.charAt(s) == T.charAt(t)) ? 0 : 5))) { RS += String.valueOf(S.charAt(s)); RT += String.valueOf(T.charAt(t)); dfs(s + 1, t + 1, 0); } else if (s < N && ret == (dpdp(s + 1, t, 2) + ((st == 2) ? 2 : 9))) { RS += String.valueOf(S.charAt(s)); RT = "-"; dfs(s + 1, t, 2); } else if (t < M && ret == (dpdp(s, t + 2, 1) + ((st == 1) ? 2 : 9))) { RS += "-"; RT += String.valueOf(T.charAt(t)); dfs(s, t + 1, 1); } } }