tmp/tmphtpmg6rl/{from.md → to.md}
RENAMED
|
@@ -0,0 +1,77 @@
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
+
#### Class template `boyer_moore_horspool_searcher` <a id="func.search.bmh">[[func.search.bmh]]</a>
|
| 2 |
+
|
| 3 |
+
``` cpp
|
| 4 |
+
template <class RandomAccessIterator1,
|
| 5 |
+
class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
|
| 6 |
+
class BinaryPredicate = equal_to<>>
|
| 7 |
+
class boyer_moore_horspool_searcher {
|
| 8 |
+
public:
|
| 9 |
+
boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
|
| 10 |
+
RandomAccessIterator1 pat_last,
|
| 11 |
+
Hash hf = Hash(),
|
| 12 |
+
BinaryPredicate pred = BinaryPredicate());
|
| 13 |
+
|
| 14 |
+
template <class RandomAccessIterator2>
|
| 15 |
+
pair<RandomAccessIterator2, RandomAccessIterator2>
|
| 16 |
+
operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
|
| 17 |
+
|
| 18 |
+
private:
|
| 19 |
+
RandomAccessIterator1 pat_first_; // exposition only
|
| 20 |
+
RandomAccessIterator1 pat_last_; // exposition only
|
| 21 |
+
Hash hash_; // exposition only
|
| 22 |
+
BinaryPredicate pred_; // exposition only
|
| 23 |
+
};
|
| 24 |
+
```
|
| 25 |
+
|
| 26 |
+
``` cpp
|
| 27 |
+
boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
|
| 28 |
+
RandomAccessIterator1 pat_last,
|
| 29 |
+
Hash hf = Hash(),
|
| 30 |
+
BinaryPredicate pred = BinaryPredicate());
|
| 31 |
+
```
|
| 32 |
+
|
| 33 |
+
*Requires:* The value type of `RandomAccessIterator1` shall meet the
|
| 34 |
+
`DefaultConstructible`, `CopyConstructible`, and `CopyAssignable`
|
| 35 |
+
requirements.
|
| 36 |
+
|
| 37 |
+
*Requires:* For any two values `A` and `B` of the type
|
| 38 |
+
`iterator_traits<RandomAccessIterator1>::value_type`, if
|
| 39 |
+
`pred(A, B) == true`, then `hf(A) == hf(B)` shall be `true`.
|
| 40 |
+
|
| 41 |
+
*Effects:* Constructs a `boyer_moore_horspool_searcher` object,
|
| 42 |
+
initializing `pat_first_` with `pat_first`, `pat_last_` with `pat_last`,
|
| 43 |
+
`hash_` with `hf`, and `pred_` with `pred`.
|
| 44 |
+
|
| 45 |
+
*Throws:* Any exception thrown by the copy constructor of
|
| 46 |
+
`RandomAccessIterator1`, or by the default constructor, copy
|
| 47 |
+
constructor, or the copy assignment operator of the value type of
|
| 48 |
+
`RandomAccessIterator1` or the copy constructor or `operator()` of
|
| 49 |
+
`BinaryPredicate` or `Hash`. May throw `bad_alloc` if additional memory
|
| 50 |
+
needed for internal data structures cannot be allocated.
|
| 51 |
+
|
| 52 |
+
``` cpp
|
| 53 |
+
template <class RandomAccessIterator2>
|
| 54 |
+
pair<RandomAccessIterator2, RandomAccessIterator2>
|
| 55 |
+
operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
|
| 56 |
+
```
|
| 57 |
+
|
| 58 |
+
*Requires:* `RandomAccessIterator1` and `RandomAccessIterator2` shall
|
| 59 |
+
have the same value type.
|
| 60 |
+
|
| 61 |
+
*Effects:* Finds a subsequence of equal values in a sequence.
|
| 62 |
+
|
| 63 |
+
*Returns:* A pair of iterators `i` and `j` such that
|
| 64 |
+
|
| 65 |
+
- `i` is the first iterator `i` in the range \[`first`,
|
| 66 |
+
`last - (pat_last_ - pat_first_)`) such that for every non-negative
|
| 67 |
+
integer `n` less than `pat_last_ - pat_first_` the following condition
|
| 68 |
+
holds: `pred(*(i + n), *(pat_first_ + n)) != false`, and
|
| 69 |
+
- `j == next(i, distance(pat_first_, pat_last_))`.
|
| 70 |
+
|
| 71 |
+
Returns `make_pair(first, first)` if \[`pat_first_`, `pat_last_`) is
|
| 72 |
+
empty, otherwise returns `make_pair(last, last)` if no such iterator is
|
| 73 |
+
found.
|
| 74 |
+
|
| 75 |
+
*Complexity:* At most `(last - first) * (pat_last_ - pat_first_)`
|
| 76 |
+
applications of the predicate.
|
| 77 |
+
|