/**
* Calculate the LCS (longest common subsequence) of two strings.
* @see http://e...content-available-to-author-only...a.org/wiki/Longest_common_subsequence_problem#Solution_for_two_sequences
* @see http://e...content-available-to-author-only...s.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence#C.2B.2B
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
template <class T> class matrix {
protected:
uint myRows, myCols;
vector<T> myData;
public:
matrix<T> () {}
matrix<T> (uint rows, uint cols):
myRows(rows), myCols(cols),
myData(rows*cols) {}
void resize (int rows, int cols) {
myRows=rows; myCols=cols;
myData.resize(rows*cols);
}
T& at(uint row, uint col) { return myData[row*myCols+col]; }
const T& at(uint row, uint col) const { return myData[row*myCols+col]; }
void fill (T value) { ::fill(myData.begin(), myData.end(), value); }
void print(ostream& out) const {
for (uint row=0; row<myRows; ++row) {
const T* temp = &myData[row*myCols];
for (uint col=0; col<myCols; ++col) {
out << temp[col] << " ";
}
out << endl;
}
}
friend ostream& operator<< (ostream& out, const matrix<T>& m) { m.print(out); return out; }
};
/** Compute the longest common subsequence between X and Y
* On return, C will contain the LCS table.
* @return C[m][n], that is the length of the longest common subsequence.
* @see http://e...content-available-to-author-only...s.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence#C.2B.2B
*/
template<typename Iterator> size_t
LCSLength(matrix<size_t>& C, Iterator X, Iterator Xend, Iterator Y, Iterator Yend) {
size_t m = std::distance(X, Xend);
size_t n = std::distance(Y, Yend);
C.resize(m+1, n+1);
// Initialize the zeroth row and zeroth column:
for (size_t i=0; i<=m; ++i)
C.at(i,0) = 0;
for (size_t j=0; j<=n; ++j)
C.at(0,j) = 0;
for (size_t i=0; i<m; ++i)
for (size_t j=0; j<n; ++j)
if (X[i] == Y[j])
C.at(i+1,j+1) = C.at(i,j) + 1;
else
C.at(i+1,j+1) = std::max(C.at(i+1,j), C.at(i,j+1));
return C.at(m,n);
}
template<typename Iterator> size_t LCSLength(Iterator X, Iterator Xend, Iterator Y, Iterator Yend) {
matrix<size_t> C;
return LCSLength(C, X, Xend, Y, Yend);
}
template<typename Iterator> size_t editDistance(Iterator X, Iterator Xend, Iterator Y, Iterator Yend) {
matrix<size_t> C;
size_t m = std::distance(X, Xend);
size_t n = std::distance(Y, Yend);
return m+n-2*LCSLength(C, X, Xend, Y, Yend);
}
#define SIZE 50
int main() {
matrix<size_t> C;
char X[] = "XMJYAUZ";
char Y[] = "MZJAWXU";
size_t length = LCSLength(C, X, X+strlen(X), Y, Y+strlen(Y));
size_t edit_distance = editDistance(X, X+strlen(X), Y, Y+strlen(Y));
cout << "length=" << length << " edit distance=" << edit_distance << endl << C;
}
LyoqCiAqIENhbGN1bGF0ZSB0aGUgTENTIChsb25nZXN0IGNvbW1vbiBzdWJzZXF1ZW5jZSkgb2YgdHdvIHN0cmluZ3MuCiAqIEBzZWUgaHR0cDovL2UuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEub3JnL3dpa2kvTG9uZ2VzdF9jb21tb25fc3Vic2VxdWVuY2VfcHJvYmxlbSNTb2x1dGlvbl9mb3JfdHdvX3NlcXVlbmNlcwogKiBAc2VlIGh0dHA6Ly9lLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5zLm9yZy93aWtpL0FsZ29yaXRobV9pbXBsZW1lbnRhdGlvbi9TdHJpbmdzL0xvbmdlc3RfY29tbW9uX3N1YnNlcXVlbmNlI0MuMkIuMkIKICovCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzdHJpbmcuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnRlbXBsYXRlIDxjbGFzcyBUPiBjbGFzcyBtYXRyaXggewpwcm90ZWN0ZWQ6CiAgdWludCBteVJvd3MsIG15Q29sczsKICB2ZWN0b3I8VD4gbXlEYXRhOwpwdWJsaWM6CiAgbWF0cml4PFQ+ICgpIHt9CiAgbWF0cml4PFQ+ICh1aW50IHJvd3MsIHVpbnQgY29scyk6IAogICAgbXlSb3dzKHJvd3MpLCBteUNvbHMoY29scyksCiAgICBteURhdGEocm93cypjb2xzKSB7fSAKIAogIHZvaWQgcmVzaXplIChpbnQgcm93cywgaW50IGNvbHMpIHsKICAgIG15Um93cz1yb3dzOyBteUNvbHM9Y29sczsKICAgIG15RGF0YS5yZXNpemUocm93cypjb2xzKTsKICB9CiAKICBUJiBhdCh1aW50IHJvdywgdWludCBjb2wpIHsgcmV0dXJuIG15RGF0YVtyb3cqbXlDb2xzK2NvbF07IH0KICBjb25zdCBUJiBhdCh1aW50IHJvdywgdWludCBjb2wpIGNvbnN0IHsgcmV0dXJuIG15RGF0YVtyb3cqbXlDb2xzK2NvbF07IH0KIAogIHZvaWQgZmlsbCAoVCB2YWx1ZSkgeyA6OmZpbGwobXlEYXRhLmJlZ2luKCksIG15RGF0YS5lbmQoKSwgdmFsdWUpOyB9CiAKICB2b2lkIHByaW50KG9zdHJlYW0mIG91dCkgY29uc3QgewogICAgZm9yICh1aW50IHJvdz0wOyByb3c8bXlSb3dzOyArK3JvdykgewogICAgICBjb25zdCBUKiB0ZW1wID0gJm15RGF0YVtyb3cqbXlDb2xzXTsKICAgICAgZm9yICh1aW50IGNvbD0wOyBjb2w8bXlDb2xzOyArK2NvbCkgewogICAgICAgIG91dCA8PCB0ZW1wW2NvbF0gPDwgIiAiOwogICAgICB9CiAgICAgIG91dCA8PCBlbmRsOwogICAgfQogIH0KIAogIGZyaWVuZCBvc3RyZWFtJiBvcGVyYXRvcjw8IChvc3RyZWFtJiBvdXQsIGNvbnN0IG1hdHJpeDxUPiYgbSkgeyBtLnByaW50KG91dCk7IHJldHVybiBvdXQ7IH0KfTsKCi8qKiBDb21wdXRlIHRoZSBsb25nZXN0IGNvbW1vbiBzdWJzZXF1ZW5jZSBiZXR3ZWVuIFggYW5kIFkKICogT24gcmV0dXJuLCBDIHdpbGwgY29udGFpbiB0aGUgTENTIHRhYmxlLgogKiBAcmV0dXJuIENbbV1bbl0sIHRoYXQgaXMgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBjb21tb24gc3Vic2VxdWVuY2UuCiAqIEBzZWUgaHR0cDovL2UuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLnMub3JnL3dpa2kvQWxnb3JpdGhtX2ltcGxlbWVudGF0aW9uL1N0cmluZ3MvTG9uZ2VzdF9jb21tb25fc3Vic2VxdWVuY2UjQy4yQi4yQgogKi8KdGVtcGxhdGU8dHlwZW5hbWUgSXRlcmF0b3I+IHNpemVfdApMQ1NMZW5ndGgobWF0cml4PHNpemVfdD4mIEMsIEl0ZXJhdG9yIFgsIEl0ZXJhdG9yIFhlbmQsIEl0ZXJhdG9yIFksIEl0ZXJhdG9yIFllbmQpIHsKCXNpemVfdCBtID0gc3RkOjpkaXN0YW5jZShYLCBYZW5kKTsKCXNpemVfdCBuID0gc3RkOjpkaXN0YW5jZShZLCBZZW5kKTsKCUMucmVzaXplKG0rMSwgbisxKTsKCgkvLyBJbml0aWFsaXplIHRoZSB6ZXJvdGggcm93IGFuZCB6ZXJvdGggY29sdW1uOgoJZm9yIChzaXplX3QgaT0wOyBpPD1tOyArK2kpCgkgIEMuYXQoaSwwKSA9IDA7Cglmb3IgKHNpemVfdCBqPTA7IGo8PW47ICsraikKCSAgQy5hdCgwLGopID0gMDsKCglmb3IgKHNpemVfdCBpPTA7IGk8bTsgKytpKQoJICBmb3IgKHNpemVfdCBqPTA7IGo8bjsgKytqKQoJICAgIGlmIChYW2ldID09IFlbal0pCgkgICAgICBDLmF0KGkrMSxqKzEpID0gQy5hdChpLGopICsgMTsKCSAgICBlbHNlCgkgICAgICBDLmF0KGkrMSxqKzEpID0gc3RkOjptYXgoQy5hdChpKzEsaiksIEMuYXQoaSxqKzEpKTsKCQoJcmV0dXJuIEMuYXQobSxuKTsKfQoKdGVtcGxhdGU8dHlwZW5hbWUgSXRlcmF0b3I+IHNpemVfdCBMQ1NMZW5ndGgoSXRlcmF0b3IgWCwgSXRlcmF0b3IgWGVuZCwgSXRlcmF0b3IgWSwgSXRlcmF0b3IgWWVuZCkgewoJbWF0cml4PHNpemVfdD4gQzsKCXJldHVybiBMQ1NMZW5ndGgoQywgWCwgWGVuZCwgWSwgWWVuZCk7Cn0KCnRlbXBsYXRlPHR5cGVuYW1lIEl0ZXJhdG9yPiBzaXplX3QgZWRpdERpc3RhbmNlKEl0ZXJhdG9yIFgsIEl0ZXJhdG9yIFhlbmQsIEl0ZXJhdG9yIFksIEl0ZXJhdG9yIFllbmQpIHsKCW1hdHJpeDxzaXplX3Q+IEM7CglzaXplX3QgbSA9IHN0ZDo6ZGlzdGFuY2UoWCwgWGVuZCk7CglzaXplX3QgbiA9IHN0ZDo6ZGlzdGFuY2UoWSwgWWVuZCk7CglyZXR1cm4gbStuLTIqTENTTGVuZ3RoKEMsIFgsIFhlbmQsIFksIFllbmQpOwp9CgojZGVmaW5lIFNJWkUgNTAKaW50IG1haW4oKSB7CgltYXRyaXg8c2l6ZV90PiBDOwoJY2hhciBYW10gPSAiWE1KWUFVWiI7CgljaGFyIFlbXSA9ICJNWkpBV1hVIjsKCXNpemVfdCBsZW5ndGggPSBMQ1NMZW5ndGgoQywgWCwgWCtzdHJsZW4oWCksIFksIFkrc3RybGVuKFkpKTsKCXNpemVfdCBlZGl0X2Rpc3RhbmNlID0gZWRpdERpc3RhbmNlKFgsIFgrc3RybGVuKFgpLCBZLCBZK3N0cmxlbihZKSk7Cgljb3V0IDw8ICJsZW5ndGg9IiA8PCBsZW5ndGggPDwgIiBlZGl0IGRpc3RhbmNlPSIgPDwgZWRpdF9kaXN0YW5jZSA8PCBlbmRsIDw8IEM7Cn0K