Proposed resolution:

This wording is relative to N5014.

1. Modify [func.search.bm] as indicated:

   namespace std {
     template<class RandomAccessIterator1,
              class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
              class BinaryPredicate = equal_to<>>
     class boyer_moore_searcher {
     public:
       constexpr boyer_moore_searcher(RandomAccessIterator1 pat_first,
                                      RandomAccessIterator1 pat_last,
                                      Hash hf = Hash(),
                                      BinaryPredicate pred = BinaryPredicate());
   
       template<class RandomAccessIterator2>
         constexpr pair<RandomAccessIterator2, RandomAccessIterator2>
           operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   
     private:
       RandomAccessIterator1 pat_first_;   // exposition only
       RandomAccessIterator1 pat_last_;    // exposition only
       Hash hash_;                         // exposition only
       BinaryPredicate pred_;              // exposition only
     };
   }
   

   constexpr boyer_moore_searcher(RandomAccessIterator1 pat_first,
                                  RandomAccessIterator1 pat_last,
                                  Hash hf = Hash(),
                                  BinaryPredicate pred = BinaryPredicate());
   

   -1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.

   […]

   template<class RandomAccessIterator2>
     constexpr pair<RandomAccessIterator2, RandomAccessIterator2>
       operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   

   -5- Mandates: RandomAccessIterator1 and RandomAccessIterator2 have the same value type.

2. Modify [func.search.bmh] as indicated:

   namespace std {
     template<class RandomAccessIterator1,
              class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
              class BinaryPredicate = equal_to<>>
     class boyer_moore_horspool_searcher {
     public:
      constexpr boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
                                              RandomAccessIterator1 pat_last,
                                              Hash hf = Hash(),
                                              BinaryPredicate pred = BinaryPredicate());
   
       template<class RandomAccessIterator2>
         constexpr pair<RandomAccessIterator2, RandomAccessIterator2>
           operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   
     private:
       RandomAccessIterator1 pat_first_;   // exposition only
       RandomAccessIterator1 pat_last_;    // exposition only
       Hash hash_;                         // exposition only
       BinaryPredicate pred_;              // exposition only
     };
   }
   

   constexpr boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
                                           RandomAccessIterator1 pat_last,
                                           Hash hf = Hash(),
                                           BinaryPredicate pred = BinaryPredicate());
   

   -1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.

   […]

   template<class RandomAccessIterator2>
     constexpr pair<RandomAccessIterator2, RandomAccessIterator2>
       operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   

   -5- Mandates: RandomAccessIterator1 and RandomAccessIterator2 have the same value type.

Currently, `boyer_moore_searcher` and `boyer_moore_horspool_searcher` are not `constexpr`-friendly because their underlying implementation needs to precompute the shift table, which usually requires a `vector` or `unordered_map` to store.

Thanks to P3372R3, unordered containers are now `constexpr`-friendly. Although `std::hash` still lacks `constexpr` support, users can provide their own hash functions to use unordered containers at compile time.

Given that both `boyer_moore_searcher` and `boyer_moore_horspool_searcher` can take a custom hash, it makes perfect sense that they could be `constexpr`-friendly.

Not to mention that library implementations usually simply use arrays instead of hash tables for the common string case because characters only have 256 values, so `unordered_map` is not actually used.