fork(4) download
copy 
  1. /**
  2.  * Calculate the LCS (longest common subsequence) of two strings.
  3.  * @see http://e...content-available-to-author-only...a.org/wiki/Longest_common_subsequence_problem#Solution_for_two_sequences
  4.  * @see http://e...content-available-to-author-only...s.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence#C.2B.2B
  5.  */
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <string.h>
  11. using namespace std;
  12.  
  13. template <class T> class matrix {
  14. protected:
  15.   uint myRows, myCols;
  16.   vector<T> myData;
  17. public:
  18.   matrix<T> () {}
  19.   matrix<T> (uint rows, uint cols): 
  20.     myRows(rows), myCols(cols),
  21.     myData(rows*cols) {} 
  22.  
  23.   void resize (int rows, int cols) {
  24.     myRows=rows; myCols=cols;
  25.     myData.resize(rows*cols);
  26.   }
  27.  
  28.   T& at(uint row, uint col) { return myData[row*myCols+col]; }
  29.   const T& at(uint row, uint col) const { return myData[row*myCols+col]; }
  30.  
  31.   void fill (T value) { ::fill(myData.begin(), myData.end(), value); }
  32.  
  33.   void print(ostream& out) const {
  34.     for (uint row=0; row<myRows; ++row) {
  35.       const T* temp = &myData[row*myCols];
  36.       for (uint col=0; col<myCols; ++col) {
  37.         out << temp[col] << " ";
  38.       }
  39.       out << endl;
  40.     }
  41.   }
  42.  
  43.   friend ostream& operator<< (ostream& out, const matrix<T>& m) { m.print(out); return out; }
  44. };
  45.  
  46. /** Compute the longest common subsequence between X and Y
  47.  * On return, C will contain the LCS table.
  48.  * @return C[m][n], that is the length of the longest common subsequence.
  49.  * @see http://e...content-available-to-author-only...s.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence#C.2B.2B
  50.  */
  51. template<typename Iterator> size_t
  52. LCSLength(matrix<size_t>& C, Iterator X, Iterator Xend, Iterator Y, Iterator Yend) {
  53. 	size_t m = std::distance(X, Xend);
  54. 	size_t n = std::distance(Y, Yend);
  55. 	C.resize(m+1, n+1);
  56.  
  57. 	// Initialize the zeroth row and zeroth column:
  58. 	for (size_t i=0; i<=m; ++i)
  59. 	  C.at(i,0) = 0;
  60. 	for (size_t j=0; j<=n; ++j)
  61. 	  C.at(0,j) = 0;
  62.  
  63. 	for (size_t i=0; i<m; ++i)
  64. 	  for (size_t j=0; j<n; ++j)
  65. 	    if (X[i] == Y[j])
  66. 	      C.at(i+1,j+1) = C.at(i,j) + 1;
  67. 	    else
  68. 	      C.at(i+1,j+1) = std::max(C.at(i+1,j), C.at(i,j+1));
  69.  
  70. 	return C.at(m,n);
  71. }
  72.  
  73. template<typename Iterator> size_t LCSLength(Iterator X, Iterator Xend, Iterator Y, Iterator Yend) {
  74. 	matrix<size_t> C;
  75. 	return LCSLength(C, X, Xend, Y, Yend);
  76. }
  77.  
  78. template<typename Iterator> size_t editDistance(Iterator X, Iterator Xend, Iterator Y, Iterator Yend) {
  79. 	matrix<size_t> C;
  80. 	size_t m = std::distance(X, Xend);
  81. 	size_t n = std::distance(Y, Yend);
  82. 	return m+n-2*LCSLength(C, X, Xend, Y, Yend);
  83. }
  84.  
  85. #define SIZE 50
  86. int main() {
  87. 	matrix<size_t> C;
  88. 	char X[] = "XMJYAUZ";
  89. 	char Y[] = "MZJAWXU";
  90. 	size_t length = LCSLength(C, X, X+strlen(X), Y, Y+strlen(Y));
  91. 	size_t edit_distance = editDistance(X, X+strlen(X), Y, Y+strlen(Y));
  92. 	cout << "length=" << length << " edit distance=" << edit_distance << endl << C;
  93. }
  94.  
Success #stdin #stdout 0s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
length=4 edit distance=6
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 1 
0 1 1 1 1 1 1 1 
0 1 1 2 2 2 2 2 
0 1 1 2 2 2 2 2 
0 1 1 2 3 3 3 3 
0 1 1 2 3 3 3 4 
0 1 2 2 3 3 3 4
https://ideone.com/iMOq3
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!