1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| class Cell{
public:
enum class Direction {none, left, diagonal, above};
private:
double valeur;
Direction direction;
static Direction bestDirectionOf(double left, double diag, double above)
if(left<diag){
return diag<above? Direction::above : Direction::diagonal;
} else {
return left<above? Direction::above : Direction::left;
}
}
static double bestOf{double left, double diag, double above
if(left<diag){
return diag<above? above : diagonal;
} else {
return left<above? above : left;
}
}
public:
Cell() : valeur(0), direction(Direction::none) {}
explicit Cell(float) : valeur(v), direction(Direction::none){}
Cell(double left, double diag, double above) :
valeur( bestOf(left, diag, above) ),
direction( bestDirectionOf(left, diag, above) )
{}
double value() const {return valeur;}
Direction direction() const {return direction;}
};
inline std::ostream& operator<<(std::ostream& os, Cell c) {
out << (c.value());
switch(c.direction()){
case Direction::left : return out<<" left";
case Direction::diagonal : return out<<" diag";
case Direction::above : return out<<" above";
}
return out;
}
using namespace boost::numeric::ublas;
void f(const QString& str1, const QString& str2) {
out << str1<<"\r\n"<<str2<<"\r\n\r\n";
matrix<Cell> m (str1.size()+1, str2.size()+1);
// Initialiser le tableau
for(size_t i=0; i<m.size1(); ++i) m(i,0)= Cell(-i);
for(size_t i=1; i<m.size2(); ++i) m(0,i)= Cell(-i);
// Calcul
for(size_t i=1; i<m.size1(); ++i) {
for(size_t j=1; j<m.size2() ;++j) {
double diag = m(i-1, j-1).value() + ( (str1[i-1]==str2[j-1])? 1 : 0);
double left = m(i-1, j).value() - 1;
doubleabove = m(i, j-1).value() - 1;
// Ici, je choisis le plus grand résultat et la direction.
m(i, j) = Cell(left, diag, above);
}
}
//affichage
out<<" ";
for(size_t j=0; j<m.size2(); ++j) out << str2[j] << " ";
out << "\r\n";
for(size_t i=0; i<m.size1(); ++i) {
out <<((i==0)?' ':str1[i-1])<<' ';
for(size_t j=0; j<m.size2(); ++j) out << m(i,j)<<' ';
out <<"\r\n";
}
} |
