| 44 | |
| 45 | template <typename Char, typename CostFn> |
| 46 | uint32_t StringMatchCost(Char const * sA, size_t sizeA, Char const * sB, size_t sizeB, CostFn const & costF, |
| 47 | uint32_t maxCost, bool bPrefixMatch = false) |
| 48 | { |
| 49 | std::priority_queue<impl::MatchCostData, buffer_vector<impl::MatchCostData, 256>> q; |
| 50 | q.push(impl::MatchCostData(0, 0, 0)); |
| 51 | while (!q.empty()) |
| 52 | { |
| 53 | uint32_t a = q.top().m_A; |
| 54 | uint32_t b = q.top().m_B; |
| 55 | uint32_t const c = q.top().m_Cost; |
| 56 | q.pop(); |
| 57 | while (a < sizeA && b < sizeB && sA[a] == sB[b]) |
| 58 | { |
| 59 | ++a; |
| 60 | ++b; |
| 61 | } |
| 62 | |
| 63 | if (a == sizeA && (bPrefixMatch || b == sizeB)) |
| 64 | return c; |
| 65 | |
| 66 | if (a < sizeA) |
| 67 | impl::PushMatchCost(q, maxCost, a + 1, b, c + costF.Cost10(sA[a])); |
| 68 | if (b < sizeB) |
| 69 | impl::PushMatchCost(q, maxCost, a, b + 1, c + costF.Cost01(sB[b])); |
| 70 | if (a < sizeA && b < sizeB) |
| 71 | impl::PushMatchCost(q, maxCost, a + 1, b + 1, c + costF.Cost11(sA[a], sB[b])); |
| 72 | if (a + 1 < sizeA && b < sizeB) |
| 73 | impl::PushMatchCost(q, maxCost, a + 2, b + 1, c + costF.Cost21(&sA[a], sB[b])); |
| 74 | if (a < sizeA && b + 1 < sizeB) |
| 75 | impl::PushMatchCost(q, maxCost, a + 1, b + 2, c + costF.Cost12(sA[a], &sB[b])); |
| 76 | if (a + 1 < sizeA && b + 1 < sizeB) |
| 77 | { |
| 78 | impl::PushMatchCost(q, maxCost, a + 2, b + 2, c + costF.Cost22(&sA[a], &sB[b])); |
| 79 | if (sA[a] == sB[b + 1] && sA[a + 1] == sB[b]) |
| 80 | impl::PushMatchCost(q, maxCost, a + 2, b + 2, c + costF.SwapCost(sA[a], sA[a + 1])); |
| 81 | } |
| 82 | } |
| 83 | return maxCost + 1; |
| 84 | } |
| 85 | } // namespace search |