Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- namespace Second
- {
- internal class Program
- {
- static void Main(string[] args)
- {
- var list = Console.ReadLine().Split().Select(int.Parse).ToArray();
- var list2 = Console.ReadLine().Split().Select(int.Parse).ToArray();
- var lcs = LCS(list, list2);
- var res = BackTrack(lcs, list, list2, list.Length, list2.Length).TrimStart(); //out
- var result = res.Split().Select(int.Parse).ToArray();
- Console.WriteLine(String.Join(" ", result));
- Console.WriteLine(result.Length);
- }
- static int[,] LCS(int[] s1, int[] s2)
- {
- int[,] c = new int[s1.Length + 1, s2.Length + 1];
- for (int i = 1; i <= s1.Length; i++)
- for (int j = 1; j <= s2.Length; j++)
- {
- if (s1[i - 1] == s2[j - 1])
- c[i, j] = c[i - 1, j - 1] + 1;
- else
- c[i, j] = c[i - 1, j] > c[i, j - 1] ? c[i - 1, j] : c[i, j - 1];
- }
- return c;
- }
- static string BackTrack(int[,] c, int[] s1, int[] s2, int i, int j)
- {
- if (i == 0 || j == 0)
- return "";
- else if (s1[i - 1] == s2[j - 1])
- return BackTrack(c, s1, s2, i - 1, j - 1) + " " + s1[i - 1];
- else if (c[i, j - 1] > c[i - 1, j])
- return BackTrack(c, s1, s2, i, j - 1);
- else
- return BackTrack(c, s1, s2, i - 1, j);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement