C++: разбить строку на словарные части

Задача состоит в том, чтобы разделить заданную строку на части-"слоги", список которых определён заранее, или сделать вывод о невозможности такого разбиения.

Словарь понимаем просто как стандартное множество <set> "слогов", реального словаря не подключаем.

Чтобы это заработало, мне пришлось включить в консольном проекте актуальной версии Visual Studio 2019 поддержку стандарта C++17 (выбрать в меню Проект, Свойства, далее как на скрине):

Как включить поддержку стандарта C++17 в Visual Studio

По умолчанию в Studio подключён стандарт C++14. Далее приводится листинг программы.

#include <iostream>
#include <optional>
#include <set>
#include <string>
#include <string_view>
#include <vector>
#include <Windows.h>
using namespace std;

struct string_comparator {
 using is_transparent = void;
 bool operator()(const string& lhs, const string& rhs) const {
  return lhs < rhs;
 }
 bool operator()(const string& lhs, const string_view& rhs) const {
  return lhs < rhs;
 }
 bool operator()(const string_view& lhs, const string& rhs) const {
  return lhs < rhs;
 }
};

using dictionary = set<string, string_comparator>;

template <typename iterator, typename separator>
string join(iterator begin, iterator end, separator sep) {
 string result;
 if (begin != end) {
  result += *begin++;
  for (; begin != end; ++begin) {
   result += sep;
   result += *begin;
  }
 }
 return result;
}

auto create_string (const string_view& s, const vector<optional<size_t>>& v) {
 auto idx = s.size();
 vector <string_view> sv;
 while (v[idx].has_value()) {
  size_t prev = v[idx].value();
  sv.push_back(s.substr(prev, idx - prev));
  idx = prev;
 }
 reverse(sv.begin(), sv.end());
 return join(sv.begin(), sv.end(), ' ');
}

optional <string> word_break(const string_view& str,
 const dictionary& dict) {
 auto size = str.size() + 1;
 vector<optional<size_t>> possible(size);
 auto check_word = [&dict, &str](size_t i, size_t j)
  -> optional<size_t> {
  if (dict.find(str.substr(i, j - i)) != dict.end())
   return i;
   return nullopt;
 };
 for (size_t i = 1; i < size; ++i) {
  if (!possible[i].has_value())
   possible[i] = check_word(0, i);
  if (possible[i].has_value()) {
   for (size_t j = i + 1; j < size; ++j) {
    if (!possible[j].has_value())
     possible[j] = check_word(i, j);
   }
   if (possible[str.size()].has_value())
    return create_string(str, possible);
  }
 }
 return nullopt;
}

int main() {
 SetConsoleCP(1251); SetConsoleOutputCP(1251);

 dictionary dict;
 //Заменить чтением словаря слогов
 dict.insert("ма");
 dict.insert("мы");
 dict.insert("ра");
 dict.insert("му");
 dict.insert("ла");
 //Простейший тест
 auto result = word_break("мамамылараму", dict);
 if (result.has_value())
  cout << result.value() << endl;
 else
  cout << "Не могу разбить строку по данному словарю" << endl;
 return 0;
}

30.09.2021, 15:04 [906 просмотров]