Advertisement
IvetValcheva

3ta

Oct 8th, 2022
688
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.62 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace Second
  6. {
  7.     internal class Program
  8.     {
  9.         static void Main(string[] args)
  10.         {
  11.             var list = Console.ReadLine().Split().Select(int.Parse).ToArray();
  12.             var list2 = Console.ReadLine().Split().Select(int.Parse).ToArray();
  13.             var lcs = LCS(list, list2);
  14.             var res = BackTrack(lcs, list, list2, list.Length, list2.Length).TrimStart(); //out
  15.             var result = res.Split().Select(int.Parse).ToArray();
  16.             Console.WriteLine(String.Join(" ", result));
  17.             Console.WriteLine(result.Length);
  18.         }
  19.  
  20.         static int[,] LCS(int[] s1, int[] s2)
  21.         {
  22.             int[,] c = new int[s1.Length + 1, s2.Length + 1];
  23.             for (int i = 1; i <= s1.Length; i++)
  24.                 for (int j = 1; j <= s2.Length; j++)
  25.                 {
  26.                     if (s1[i - 1] == s2[j - 1])
  27.                         c[i, j] = c[i - 1, j - 1] + 1;
  28.                     else
  29.                         c[i, j] = c[i - 1, j] > c[i, j - 1] ? c[i - 1, j] : c[i, j - 1];
  30.                 }
  31.             return c;
  32.         }
  33.  
  34.         static string BackTrack(int[,] c, int[] s1, int[] s2, int i, int j)
  35.         {
  36.             if (i == 0 || j == 0)
  37.                 return "";
  38.             else if (s1[i - 1] == s2[j - 1])
  39.                 return BackTrack(c, s1, s2, i - 1, j - 1) + " " + s1[i - 1];
  40.             else if (c[i, j - 1] > c[i - 1, j])
  41.                 return BackTrack(c, s1, s2, i, j - 1);
  42.             else
  43.                 return BackTrack(c, s1, s2, i - 1, j);
  44.         }
  45.     }
  46. }
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement