LCS header file


/ Published in: C++
Save to your folder(s)



Copy this code and paste it in your HTML
  1. /*
  2.  * =====================================================================================
  3.  *
  4.  * Filename: lcs.hpp
  5.  *
  6.  * Description: A class of longest common subsequence (lcs) by dynamic programming
  7.  *
  8.  * Version: 1.2
  9.  * Created: 2011å¹´01月03æ—¥ 20時15分32秒
  10.  * Revision: none
  11.  * Compiler: gcc
  12.  *
  13.  * Author: Dirk Chang (), [email protected]
  14.  * Company: lc.asiahope.net
  15.  *
  16.  * =====================================================================================
  17.  */
  18. #ifndef LCS_HPP_
  19. #define LCS_HPP_
  20.  
  21. #include <vector>
  22. #include <iostream>
  23. #include <iomanip>
  24. #include <cstring>
  25. #include <iterator>
  26. #include <algorithm>
  27.  
  28. struct Default_LCS_Comparison {
  29. template <typename T>
  30. static bool equal(T const &x, T const &y) {
  31. return x == y; // use operator == as the default comparison funtion
  32. }
  33. };
  34.  
  35. template <typename COMP = Default_LCS_Comparison>
  36. class LCS {
  37. private:
  38. enum Direction { NIL = 0, LEFT, UPLEFT, UP };
  39. typedef size_t IndexType;
  40. typedef IndexType* Row;
  41. typedef std::vector<Row> Table;
  42. typedef std::vector<Direction*> AnsTable;
  43.  
  44. public:
  45. LCS(size_t const & reserved = 32) : _length(0), _m(0), _n(0), _reserved(reserved+1) {
  46. construct_table();
  47. }
  48. ~LCS() {
  49. destory_table();
  50. }
  51. LCS(LCS const &l) : _length(l._length), _reserved(l._reserved) {
  52. construct_table();
  53. for(size_t i = 0; i < _reserved; ++i) {
  54. std::memcpy(_compute_table[i], l._compute_table[i], sizeof(IndexType)*_reserved);
  55. std::memcpy(_answer_table[i], l._answer_table[i], sizeof(Direction)*_reserved);
  56. }
  57. }
  58. LCS const &operator=(LCS const &l) {
  59. _length = l._length;
  60. _reserved = l._reserved;
  61. destory_table();
  62. construct_table();
  63. for(size_t i = 0; i < _reserved; ++i) {
  64. std::memcpy(_compute_table[i], l._compute_table[i], sizeof(IndexType)*_reserved);
  65. std::memcpy(_answer_table[i], l._answer_table[i], sizeof(Direction)*_reserved);
  66. }
  67. }
  68.  
  69. template<typename const_iterator>
  70. inline IndexType Compute(const_iterator x_begin, const_iterator x_end, size_t const x_size, const_iterator y_begin, const_iterator y_end, size_t const y_size) {
  71. _length = 0;
  72. _m = x_size;
  73. _n = y_size;
  74.  
  75. size_t tmp_max = y_size;
  76. if(tmp_max < x_size) tmp_max = x_size;
  77. if(tmp_max >= _reserved) {
  78. _reserved = tmp_max + 1;
  79. destory_table();
  80. construct_table();
  81. }
  82.  
  83. const_iterator xi, yj;
  84. xi = x_begin;
  85. size_t i(1), j(1);
  86. for(i = 1; i <= x_size; ++i) {
  87. yj = y_begin;
  88. for(j = 1; j <= y_size; ++j) {
  89. if(COMP::equal(*xi,*yj)) {
  90. _compute_table[i][j] = _compute_table[i - 1][j - 1] + 1;
  91. _answer_table[i][j] = UPLEFT;
  92. }
  93. else if(_compute_table[i - 1][j] >= _compute_table[i][j - 1]) {
  94. _compute_table[i][j] = _compute_table[i - 1][j];
  95. _answer_table[i][j] = UP;
  96. }
  97. else {
  98. _compute_table[i][j] = _compute_table[i][j - 1];
  99. _answer_table[i][j] = LEFT;
  100. }
  101. ++yj;
  102. }
  103. ++xi;
  104. }
  105. _length = _compute_table[x_size][y_size];
  106. return _length;
  107. }
  108.  
  109. inline IndexType Length() {
  110. return _length;
  111. }
  112.  
  113. template<typename SEQ, typename ANS>
  114. int Answer(const SEQ &x, ANS &answer) {
  115. construct_answer(x, _m, _n, answer);
  116. return 0;
  117. }
  118.  
  119. void PrintComputeTable(std::ostream &out, int const tab = 2);
  120. void PrintAnswerTable(std::ostream &out, int const tab = 2);
  121.  
  122. private:
  123. template<typename SEQ, typename ANS>
  124. void construct_answer(const SEQ &x, int const i, int const j, ANS &answer) {
  125. if(i == 0 || j == 0) return;
  126. if(_answer_table[i][j] == UPLEFT) {
  127. construct_answer(x, i - 1, j - 1, answer);
  128. answer.push_back(x[i - 1]);
  129. }
  130. else if(_answer_table[i][j] == UP) {
  131. construct_answer(x, i - 1, j, answer);
  132. }
  133. else construct_answer(x, i, j - 1, answer);
  134. }
  135.  
  136. void construct_table() {
  137. _compute_table.resize(_reserved, 0);
  138. _answer_table.resize(_reserved, 0);
  139. for(size_t i = 0; i < _reserved; ++i) {
  140. _compute_table[i] = new IndexType [_reserved];
  141. _answer_table[i] = new Direction [_reserved];
  142. _compute_table[i][0] = 0;
  143. _answer_table[i][0] = NIL;
  144. }
  145. for(size_t i = 0; i < _reserved; ++i) {
  146. _compute_table[0][i] = 0;
  147. _answer_table[0][i] = NIL;
  148. }
  149. }
  150. void destory_table() {
  151. for(size_t i = 0; i < _reserved; ++i) {
  152. delete [] _compute_table[i];
  153. delete [] _answer_table[i];
  154. }
  155. }
  156.  
  157. private:
  158. Table _compute_table;
  159. AnsTable _answer_table;
  160. IndexType _length, _m, _n;
  161. size_t _reserved;
  162. };
  163.  
  164. template <typename COMP>
  165. void LCS<COMP>::PrintAnswerTable(std::ostream &out, int const tab) {
  166. int i, j;
  167. out << std::setw(tab) << ' ' << std::setw(tab) << 'j';
  168. for(i = 0; i < _n; ++i) {
  169. out << std::setw(tab) << i;
  170. }
  171. out << '\n';
  172.  
  173. out << std::setw(tab) << 'i' << std::setw(tab) << ' ' << std::setw(tab) << 'y' << '\n';
  174. out << std::setw(tab) << '0' << std::setw(tab) << 'x';
  175. for(i = 0; i< _n; ++i) {
  176. out << std::setw(tab) << '0';
  177. }
  178. out << '\n';
  179.  
  180. for(i = 1; i < _m; ++i) {
  181. out << std::setw(tab) << i << std::setw(tab) << ' ';
  182. for(j = 0; j < _n; ++j) {
  183. out << std::setw(tab) << _answer_table[i][j];
  184. }
  185. out << '\n';
  186. }
  187. out << '\n';
  188. }
  189.  
  190.  
  191. template <typename COMP>
  192. void LCS<COMP>::PrintComputeTable(std::ostream &out, int const tab) {
  193. int i, j;
  194. out << std::setw(tab) << ' ' << std::setw(tab) << 'j';
  195. for(i = 0; i < _n; ++i) {
  196. out << std::setw(tab) << i;
  197. }
  198. out << '\n';
  199.  
  200. out << std::setw(tab) << 'i' << std::setw(tab) << ' ' << std::setw(tab) << 'y' << '\n';
  201. out << std::setw(tab) << '0' << std::setw(tab) << 'x';
  202. for(i = 0; i< _n; ++i) {
  203. out << std::setw(tab) << '0';
  204. }
  205. out << '\n';
  206.  
  207. for(i = 1; i < _m; ++i) {
  208. out << std::setw(tab) << i << std::setw(tab) << ' ';
  209. for(j = 0; j < _n; ++j) {
  210. out << std::setw(tab) << _compute_table[i][j];
  211. }
  212. out << '\n';
  213. }
  214. out << '\n';
  215. }
  216.  
  217. template <typename COMP = Default_LCS_Comparison>
  218. class LCS_NOANS {
  219. private:
  220. typedef size_t IndexType;
  221. typedef IndexType* Row;
  222. typedef std::vector<Row> Table;
  223.  
  224. public:
  225. LCS_NOANS(size_t const & reserved = 32) : _length(-1), _reserved(reserved+1) {
  226. _compute_table.resize(2, 0);
  227. _compute_table[0] = new IndexType [_reserved];
  228. _compute_table[1] = new IndexType [_reserved];
  229. }
  230. ~LCS_NOANS() {
  231. delete [] _compute_table[0];
  232. delete [] _compute_table[1];
  233. }
  234. LCS_NOANS(LCS_NOANS const &l) : _length(l._length), _reserved(l._reserved) {
  235. _compute_table[0] = new IndexType [_reserved];
  236. _compute_table[1] = new IndexType [_reserved];
  237. std::memcpy(_compute_table[0], l._compute_table[0], sizeof(IndexType)*_reserved);
  238. std::memcpy(_compute_table[1], l._compute_table[1], sizeof(IndexType)*_reserved);
  239. }
  240. LCS_NOANS const &operator=(LCS_NOANS const &l) {
  241. _length = l._length;
  242. _reserved = l._reserved;
  243. delete [] _compute_table[0];
  244. delete [] _compute_table[1];
  245. _compute_table[0] = new IndexType [_reserved];
  246. _compute_table[1] = new IndexType [_reserved];
  247. std::memcpy(_compute_table[0], l._compute_table[0], sizeof(IndexType)*_reserved);
  248. std::memcpy(_compute_table[1], l._compute_table[1], sizeof(IndexType)*_reserved);
  249. }
  250.  
  251. template<typename const_iterator>
  252. inline IndexType Compute(const_iterator x_begin, const_iterator x_end, size_t const x_size, const_iterator y_begin, const_iterator y_end, size_t const y_size) {
  253. _length = 0;
  254.  
  255. size_t tmp_max = y_size;
  256. if(tmp_max < x_size) tmp_max = x_size;
  257. if(tmp_max >= _reserved) {
  258. _reserved = tmp_max + 1;
  259. delete [] _compute_table[0];
  260. delete [] _compute_table[1];
  261. _compute_table[0] = new IndexType [_reserved];
  262. _compute_table[1] = new IndexType [_reserved];
  263. }
  264. std::memset(_compute_table[0], 0, sizeof(IndexType)*_reserved);
  265. _compute_table[1][0] = 0;
  266.  
  267. const_iterator xi, yj;
  268. xi = x_begin;
  269. size_t i(1), j(1);
  270. for(i = 1; i <= x_size; ++i) {
  271. yj = y_begin;
  272. _compute_table[i%2][0] = 0;
  273. for(j = 1; j <= y_size; ++j) {
  274. if(i%2) {
  275. if(COMP::equal(*xi,*yj)) {
  276. //std::cout << "(" << *xi << "," << *yj << ")";
  277. _compute_table[1][j] = _compute_table[0][j - 1] + 1;
  278. }
  279. else if(_compute_table[0][j] >= _compute_table[1][j - 1]) {
  280. _compute_table[1][j] = _compute_table[0][j];
  281. }
  282. else {
  283. _compute_table[1][j] = _compute_table[1][j - 1];
  284. }
  285. }
  286. else {
  287. if(COMP::equal(*xi,*yj)) {
  288. _compute_table[0][j] = _compute_table[1][j - 1] + 1;
  289. }
  290. else if(_compute_table[1][j] >= _compute_table[0][j - 1]) {
  291. _compute_table[0][j] = _compute_table[1][j];
  292. }
  293. else {
  294. _compute_table[0][j] = _compute_table[0][j - 1];
  295. }
  296. }
  297. ++yj;
  298. }
  299. ++xi;
  300. }
  301. _length = _compute_table[x_size%2][y_size];
  302. return _length;
  303. }
  304. inline IndexType Length() {
  305. return _length;
  306. }
  307.  
  308. private:
  309. Table _compute_table;//, _answer_table;
  310. IndexType _length;
  311. size_t _reserved;
  312. };
  313.  
  314. #endif /* LCS_HPP_ */

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.