View difference between Paste ID: W5FwGYBa and 3VF7My9N
SHOW: | | - or go back to the newest paste.
1
#include <iostream>
2
#include <fstream>
3
#include <string>
4
#include <vector>
5
#include <algorithm>
6
#include <cstdint>
7
8
using namespace std;
9
10
class Matrix
11
{
12
public:
13
  Matrix(uint16_t _n, uint16_t _m)
14
    : n(_n)
15
    , m(_m)
16
  {
17
    data = new std::uint16_t[n*m];
18
  }
19
20
  ~Matrix() { delete[] data; }
21
22
  uint16_t &at(int i, int j) { return data[m*i + j]; }
23
24
private:
25
  uint16_t *data, n, m;
26
};
27
28
vector<string> linesFromFile(const char *path);
29
30
int main(int argc, char **argv)
31
{
32
  auto lines1 = linesFromFile(argv[1]);
33
  auto lines2 = linesFromFile(argv[2]);
34
  int n = lines1.size(),
35
      m = lines2.size();
36
37
  Matrix mat(n, m);
38
  for(int i = 1; i < n; i++)
39
  {
40
    for(int j = 1; j < m; j++)
41
    {
42
      uint16_t a = mat.at(i-1, j),
43
               b = mat.at(i, j-1),
44
               c = (mat.at(i-1, j-1) + 1) * uint16_t(lines1[i-1] == lines2[j-1]);
45
      mat.at(i, j) = max({a, b, c});
46
    }
47
  }
48
49
  vector<string> diff;
50
  int i = n-1, j = m-1;
51
52
  if(lines1[i] == lines2[j])
53
  {
54-
    diff.push_back("  " + lines1[i]);
54+
    diff.push_back("\e[37m" + lines1[i]);
55
  }
56
  else
57
  {
58-
    diff.push_back("- " + lines1[i]);
58+
59-
    diff.push_back("+ " + lines2[j]);
59+
60
  }
61
62
  while(i > 0 && j > 0)
63
  {
64
    auto a = mat.at(i-1, j);
65
    auto b = mat.at(i, j-1);
66
    auto c = (mat.at(i-1, j-1) + 1) * uint16_t(lines1[i-1] == lines2[j-1]);
67
    if(mat.at(i, j) == a)
68
    {
69
      i--;
70
      diff.push_back("\e[31m" + lines1[i]);
71
    }
72
    else if(mat.at(i, j) == b)
73
    {
74
      j--;
75
      diff.push_back("\e[32m" + lines2[j]);
76
    }
77
    else
78
    {
79
      i--;
80
      j--;
81
      diff.push_back("\e[37m" + lines1[i]);
82
    }
83
  }
84
85
  while(i > 0)
86
  {
87
    i--;
88
    diff.push_back("\e[31m" + lines1[i]);
89
  }
90
91
  while(j > 0)
92
  {
93
    j--;
94
    diff.push_back("\e[32m" + lines2[j]);
95
  }
96
97
  for_each(diff.rbegin(), diff.rend(), [](auto &s){cout << s << endl;});
98
99
  cout << "\e[0m";
100
}
101
102
vector<string> linesFromFile(const char *path)
103
{
104
  vector<string> ret;
105
106
  ifstream file(path);
107
  while(!file.eof())
108
  {
109
    string line;
110
    getline(file, line);
111
    ret.push_back(line);
112
  }
113
  file.close();
114
115
  return ret;
116
}
117