fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <iterator>
  5.  
  6. using std::begin;
  7. using std::endl;
  8.  
  9. // Change to Boost's boyer_moore_horspool if you need a better complexity
  10. template <typename HaystackIter, typename Needle, typename Output>
  11. void search_all(HaystackIter first, HaystackIter last, Needle &needle,
  12.                 Output out) {
  13.   for (HaystackIter it = first;
  14.        (it = std::search(it, last, begin(needle), end(needle))) != last;
  15.        it += needle.size())
  16.     *out++ = std::make_pair(it, &needle);
  17. }
  18.  
  19. template <typename C, typename I, typename Value = typename C::value_type>
  20. std::vector<Value> match_best(const C &dict, I from, I to) {
  21.   std::vector<std::pair<I, Value const *> > events;
  22.   for (auto &d : dict)
  23.     search_all(from, to, d, std::back_inserter(events));
  24.   std::sort(begin(events), end(events));
  25.   std::vector<std::pair<int, Value const *> > dp(to - from + 1, std::make_pair(std::numeric_limits<int>::min(), nullptr));
  26.   dp[0].first = 0;
  27.   for (auto &e : events) {
  28.     auto &old_res = dp[e.first - from + e.second->size()];
  29.     auto new_res = std::make_pair(dp[e.first - from].first + 1, e.second);
  30.     old_res = std::max(old_res, new_res);
  31.   }
  32.   std::vector<Value> result(std::max(0,dp.back().first));
  33.   int res_idx = result.size() - 1;
  34.   for (size_t i = dp.size() - 1; res_idx >= 0; i = i - dp[i].second->size())
  35.     result[res_idx--] = *dp[i].second;
  36.   return result;
  37. }
  38.  
  39. std::vector<std::string> match_best(std::vector<std::string> const& dict,
  40.                                     std::string const& in)
  41. {
  42.   return match_best(dict, begin(in), end(in));
  43. }
  44.  
  45. int main() {
  46.   using namespace std;
  47.   std::vector<std::string> dict = {"this", "is", "a", "awe", "we", "awesome"};
  48.   std::string test = "thisisawesome";
  49.   vector<string> words = match_best(dict, test);
  50.   copy(begin(words), end(words), ostream_iterator<string>(cout, "\n"));
  51. }
  52.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin 
Standard input is empty
stdout 
this
is
awesome
https://ideone.com/7sD7Ee
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!