#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdint>

using namespace std;

class Matrix
{
public:
  Matrix(uint16_t _n, uint16_t _m)
    : n(_n)
    , m(_m)
  {
    data = new std::uint16_t[n*m];
  }

  ~Matrix() { delete[] data; }

  uint16_t &at(int i, int j) { return data[m*i + j]; }

private:
  uint16_t *data, n, m;
};

vector<string> linesFromFile(const char *path);

int main(int argc, char **argv)
{
  auto lines1 = linesFromFile(argv[1]);
  auto lines2 = linesFromFile(argv[2]);
  int n = lines1.size(),
      m = lines2.size();

  Matrix mat(n, m);
  for(int i = 1; i < n; i++)
  {
    for(int j = 1; j < m; j++)
    {
      uint16_t a = mat.at(i-1, j),
               b = mat.at(i, j-1),
               c = (mat.at(i-1, j-1) + 1) * uint16_t(lines1[i-1] == lines2[j-1]);
      mat.at(i, j) = max({a, b, c});
    }
  }

  vector<string> diff;
  int i = n-1, j = m-1;

  if(lines1[i] == lines2[j])
  {
    diff.push_back("  " + lines1[i]);
  }
  else
  {
    diff.push_back("- " + lines1[i]);
    diff.push_back("+ " + lines2[j]);
  }

  while(i > 0 && j > 0)
  {
    auto a = mat.at(i-1, j);
    auto b = mat.at(i, j-1);
    auto c = (mat.at(i-1, j-1) + 1) * uint16_t(lines1[i-1] == lines2[j-1]);
    if(mat.at(i, j) == a)
    {
      i--;
      diff.push_back("\e[31m" + lines1[i]);
    }
    else if(mat.at(i, j) == b)
    {
      j--;
      diff.push_back("\e[32m" + lines2[j]);
    }
    else
    {
      i--;
      j--;
      diff.push_back("\e[37m" + lines1[i]);
    }
  }

  while(i > 0)
  {
    i--;
    diff.push_back("\e[31m" + lines1[i]);
  }

  while(j > 0)
  {
    j--;
    diff.push_back("\e[32m" + lines2[j]);
  }

  for_each(diff.rbegin(), diff.rend(), [](auto &s){cout << s << endl;});

  cout << "\e[0m";
}

vector<string> linesFromFile(const char *path)
{
  vector<string> ret;

  ifstream file(path);
  while(!file.eof())
  {
    string line;
    getline(file, line);
    ret.push_back(line);
  }
  file.close();

  return ret;
}