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 [968 просмотров]