#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using std::begin;
using std::endl;
 
// Change to Boost's boyer_moore_horspool if you need a better complexity
template <typename HaystackIter, typename Needle, typename Output>
void search_all(HaystackIter first, HaystackIter last, Needle &needle,
                Output out) {
  for (HaystackIter it = first;
       (it = std::search(it, last, begin(needle), end(needle))) != last;
       it += needle.size())
    *out++ = std::make_pair(it, &needle);
}
 
template <typename C, typename I, typename Value = typename C::value_type>
std::vector<Value> match_best(const C &dict, I from, I to) {
  std::vector<std::pair<I, Value const *> > events;
  for (auto &d : dict)
    search_all(from, to, d, std::back_inserter(events));
  std::sort(begin(events), end(events));
  std::vector<std::pair<int, Value const *> > dp(to - from + 1, std::make_pair(std::numeric_limits<int>::min(), nullptr));
  dp[0].first = 0;
  for (auto &e : events) {
    auto &old_res = dp[e.first - from + e.second->size()];
    auto new_res = std::make_pair(dp[e.first - from].first + 1, e.second);
    old_res = std::max(old_res, new_res);
  }
  std::vector<Value> result(std::max(0,dp.back().first));
  int res_idx = result.size() - 1;
  for (size_t i = dp.size() - 1; res_idx >= 0; i = i - dp[i].second->size())
    result[res_idx--] = *dp[i].second;
  return result;
}

std::vector<std::string> match_best(std::vector<std::string> const& dict,
                                    std::string const& in)
{
  return match_best(dict, begin(in), end(in));
}
 
int main() {
  using namespace std;
  std::vector<std::string> dict = {"this", "is", "a", "awe", "we", "awesome"};
  std::string test = "thisisawesome";
  vector<string> words = match_best(dict, test);
  copy(begin(words), end(words), ostream_iterator<string>(cout, "\n"));
}