Страницы

Поиск по вопросам

четверг, 7 марта 2019 г.

алгоритм поиска в массиве строк наиболее отличающуюся от первой

Я ищу наиболее быстрый алгоритм для поиска строки в массиве строк, которая сильнее всего отличается от первой строки массива. Строки все одинаковой длины. Позиция символов и их ASCII код имеет принципиальное значение. Если решать задачу в лоб, то нужно перебрать каждую строчку массива и сравнить каждый ее символ с символом первой строки с тем же индексом. Если они отличаются, то счетчик для этой строки массива увеличивается. Самый большой счетчик дает нам строку, которая наиболее отличается от первой.


Ответ

Можно использовать следующий алгоритм:
std::vector strings ... std::vector distances; for(size_t i = 1; i < strings.size(); ++i) { std::deque tmp(strings[i].size()); for(size_t j = 0; j < tmp.size(); ++j) tmp[j] = static_cast(strings[i][j] == strings[0][j]); auto distance = count(begin(tmp), end(tmp), false); distances.push_back(distance); } auto idx = distance(begin(distances), max_element(begin(distances), end(distances))) + 1; auto result = strings[idx];
Этот код очень легко переписать под векторные инструкции и его скорость может вырасти многократно, но для этого надо знать размер строк(Вы его знаете, я — нет)

Комментариев нет:

Отправить комментарий