Browse › Articles › 'A' Longest Common Subsequence (LCS) implementation › History › Revision 22 vs. Revision 23

Writing an article is easy - try our reStructured Text demo Join Siafoo Now or Learn More

'A' Longest Common Subsequence (LCS) implementation

Revision 22 vs. Revision 23

r22	r23
83	83	I went through a series of implementations for fun and exploration. The first and most basic was a C version for char* comparisons. The second was a C++ version which used memoization to keep track of the comparisons.
84	84
85	85	Section 2.1 C version for char*
86	86	*******************************
87	87
88		The first code I implemented was to demonstrate the memoization algorithm from the `UCI`_ article pretty much as-is (:snippet:374`). It is implemented in C.
	88	The first code I implemented was to demonstrate the memoization algorithm from the `UCI`_ article pretty much as-is (:snippet:`374`). It is implemented in C.
89	89
90	90	Section 2.2 C++ version (first try)
91	91	***********************************
92	92
93	93	The next thing I decided to do was think about this in terms of the sequence being any object. As a result I would need to think more about indices and what it meant to be at the end of a set of objects and the size of the object collection. That was too much to think about so I decided to make an LCS C++ template class that could be used for c++ containers or at least some containers. The code is here :snippet:`375` and test/example code is here :snippet:`382`.