Longest common subsequence: Difference between revisions
Resorted to verbose typedef and parameter names to help clarify their purpose.
m (Switched std::map to C++11 std::unordered_map to reduce initial Match() overhead.) |
(Resorted to verbose typedef and parameter names to help clarify their purpose.) |
||
Line 490:
typedef deque<uint32_t> THRESHOLD;
typedef deque<uint32_t> INDEXES;
typedef unordered_map<char, INDEXES>
typedef deque<INDEXES*> MATCHES;
▲ uint32_t Pairs(MATCHES& matches, shared_ptr<Pair>* pairs) {
auto trace = pairs != nullptr;
PAIRS traces;
Line 504 ⟶ 503:
//
uint32_t index1 = 0;
for (const auto& it1 :
if (!it1->empty()) {
auto dq2 = *it1;
Line 571 ⟶ 570:
//
// Match() avoids
//
//
// The lookup time can be assumed constant in the case of characters.
Line 579 ⟶ 577:
// time will be O(log(m+n)), at most.
//
void Match(
const string& s1, const string& s2) {
uint32_t index = 0;
for (const auto& it : s2)
for (const auto& it : s1) {
auto& dq2 =
}
}
Line 604 ⟶ 602:
public:
string Correspondence(const string& s1, const string& s2) {
CHAR_TO_INDEXES_MAP indexesOf2MatchedByChar;
MATCHES
Match(
shared_ptr<Pair> pairs; // obtain the LCS as index pairs
auto length = Pairs(
return Select(pairs, length, false, s1, s2);
}
| |||