Longest common subsequence: Difference between revisions
Introduced LCS::pushPair() method. Added static method declarations.
m (Added link to further C++ examples.) |
(Introduced LCS::pushPair() method. Added static method declarations.) |
||
Line 494:
=={{header|C++}}==
'''Hunt and Szymanski algorithm'''
<syntaxhighlight lang="cpp"
#include <stdint.h>
#include <string>
#include <memory> // for shared_ptr<>
Line 531 ⟶ 532:
typedef deque<INDEXES*> MATCHES;
static uint32_t FindLCS(MATCHES& indexesOf2MatchedByIndex1, shared_ptr<Pair>* pairs) {
auto traceLCS = pairs != nullptr;
PAIRS chains;
Line 555 ⟶ 556:
//
limit = lower_bound(prefixEnd.begin(), limit, index2);
auto index3 = distance(prefixEnd.begin(), limit);▼
//
Line 574:
//
if (preferNextIndex2) continue;
▲ auto index3 = distance(prefixEnd.begin(), limit);
if (limit == prefixEnd.end()) {
Line 581 ⟶ 583:
limit = prev(prefixEnd.end());
if (traceLCS) {
auto last = make_shared<Pair>(index1, index2, prefix);▼
}
}
Line 591:
*limit = index2;
if (traceLCS) {
chains[index3] = last;▼
}
}
Line 613 ⟶ 611:
}
private:
static shared_ptr<Pair> pushPair(
PAIRS& chains, const ptrdiff_t& index3, uint32_t& index1, uint32_t& index2) {
}
protected:
//
// Match() avoids m*n comparisons by using CHAR_TO_INDEXES_MAP to
Line 621 ⟶ 627:
// time will be O(log(m+n)), at most.
//
static void Match(CHAR_TO_INDEXES_MAP& indexesOf2MatchedByChar, MATCHES& indexesOf2MatchedByIndex1,
const string& s1, const string& s2) {
uint32_t index = 0;
Line 633 ⟶ 639:
}
static string Select(shared_ptr<Pair> pairs, uint32_t length,
bool right, const string& s1, const string& s2) {
string buffer;
Line 645 ⟶ 651:
public:
static string Correspondence(const string& s1, const string& s2) {
CHAR_TO_INDEXES_MAP indexesOf2MatchedByChar;
MATCHES indexesOf2MatchedByIndex1; // holds references into indexesOf2MatchedByChar
Line 655 ⟶ 661:
};</syntaxhighlight>
'''Example''':
<syntaxhighlight lang="cpp">
auto s =
cout << s << endl;</syntaxhighlight>
| |||