| 1649 | */ |
| 1650 | protected: |
| 1651 | ssize_t match_bitap(const string_t &text, const string_t &pattern, ssize_t loc) const { |
| 1652 | if (!(Match_MaxBits == 0 || (ssize_t)pattern.length() <= Match_MaxBits)) { |
| 1653 | throw string_t(traits::cs(L"Pattern too long for this application.")); |
| 1654 | } |
| 1655 | |
| 1656 | // Initialise the alphabet. |
| 1657 | std::map<char_t, ssize_t> s; |
| 1658 | match_alphabet(pattern, s); |
| 1659 | |
| 1660 | // Highest score beyond which we give up. |
| 1661 | double score_threshold = Match_Threshold; |
| 1662 | // Is there a nearby exact match? (speedup) |
| 1663 | size_t best_loc = text.find(pattern, loc); |
| 1664 | if (best_loc != string_t::npos) { |
| 1665 | score_threshold = std::min(match_bitapScore(0, best_loc, loc, pattern), |
| 1666 | score_threshold); |
| 1667 | // What about in the other direction? (speedup) |
| 1668 | best_loc = text.rfind(pattern, loc + pattern.length()); |
| 1669 | if (best_loc != string_t::npos) { |
| 1670 | score_threshold = std::min(match_bitapScore(0, best_loc, loc, pattern), |
| 1671 | score_threshold); |
| 1672 | } |
| 1673 | } |
| 1674 | |
| 1675 | // Initialise the bit arrays. |
| 1676 | ssize_t matchmask = 1 << (pattern.length() - 1); |
| 1677 | best_loc = -1; |
| 1678 | |
| 1679 | ssize_t bin_min, bin_mid; |
| 1680 | ssize_t bin_max = pattern.length() + text.length(); |
| 1681 | ssize_t *rd = NULL; |
| 1682 | ssize_t *last_rd = NULL; |
| 1683 | for (ssize_t d = 0; d < (ssize_t)pattern.length(); d++) { |
| 1684 | // Scan for the best match; each iteration allows for one more error. |
| 1685 | // Run a binary search to determine how far from 'loc' we can stray at |
| 1686 | // this error level. |
| 1687 | bin_min = 0; |
| 1688 | bin_mid = bin_max; |
| 1689 | while (bin_min < bin_mid) { |
| 1690 | if (match_bitapScore(d, loc + bin_mid, loc, pattern) |
| 1691 | <= score_threshold) { |
| 1692 | bin_min = bin_mid; |
| 1693 | } else { |
| 1694 | bin_max = bin_mid; |
| 1695 | } |
| 1696 | bin_mid = (bin_max - bin_min) / 2 + bin_min; |
| 1697 | } |
| 1698 | // Use the result from this iteration as the maximum for the next. |
| 1699 | bin_max = bin_mid; |
| 1700 | ssize_t start = std::max((ssize_t)1l, loc - bin_mid + 1); |
| 1701 | ssize_t finish = std::min(loc + bin_mid, (ssize_t)text.length()) + pattern.length(); |
| 1702 | |
| 1703 | rd = new ssize_t[finish + 2]; |
| 1704 | rd[finish + 1] = (1 << d) - 1; |
| 1705 | for (ssize_t j = finish; j >= start; j--) { |
| 1706 | ssize_t charMatch; |
| 1707 | if ((ssize_t)text.length() <= j - 1) { |
| 1708 | // Out of range. |