// Вставьте сюда финальное содержимое файла LongestCommonSubsequenceCalculator.cs
using System;
using System.Collections.Generic;

namespace Antiplagiarism
{
    public static class LongestCommonSubsequenceCalculator
    {
        public static List<string> Calculate(List<string> first, List<string> second)
        {
            var opt = CreateOptimizationTable(first, second);
            return RestoreAnswer(opt, first, second);
        }

        private static int[,] CreateOptimizationTable(List<string> first, List<string> second)
        {
            var count1 = first.Count;
            var count2 = second.Count;

            var opt = new int[count1 + 1, count2 + 1];
            opt[0, 0] = 0;

            /*Граничные случаи тривиальны: opt[0, i2] = 0, opt[i1, 0] = 0 для любых i1 и i2*/
            for (var i = 1; i <= count1; ++i) opt[i, 0] = 0;
            for (var i = 1; i <= count2; ++i) opt[0, i] = 0;

            for (int i = 1; i <= count1; ++i)

                for (int j = 1; j <= count2; ++j)
                {
                    /*Рассматриваем совпадение токенов*/
                    if (first[i - 1] == second[j - 1])
                        opt[i, j] = opt[i - 1, j - 1] + 1;
                    else
                        opt[i, j] = Math.Max(opt[i - 1, j], opt[i, j - 1]);
                }

            var result = opt;
            return result;
        }

        private static List<string> RestoreAnswer(int[,] opt, List<string> first, List<string> second)
        {
            var r = new List<string>();

            var count1 = first.Count;
            var count2 = second.Count;

            while (opt[count1, count2] != 0)
            {
                if (opt[count1 - 1, count2] >= opt[count1, count2])
                {
                    if (opt[count1 - 1, count2] >= opt[count1, count2 - 1])
                        count1--;
                    else count2--;
                }

                else if (opt[count1, count2 - 1] >= opt[count1, count2])
                {
                    if (opt[count1 - 1, count2] >= opt[count1, count2 - 1])
                        count1--;
                    else count2--;
                }

                else
                {
                    r.Add(first[count1 - 1]);
                    opt[count1, count2]--;
                    count1--; count2--;
                }
            }

            r.Reverse();
            return r;
        }
    }
}