С++, из списка слов длины 3 или 4, найти слова которые являются палиндромом
Стоит задача: Разработать функции хеширования со свойствами h(a,b,c)= h(c,b,a) и h(a,b,c,d)= h(d,c,b,a). Для списка слов из трех или четырех букв, подсчитать количество палиндромов для каждого слова. Метод разрешения коллизий – линейный.
Преподаватель объяснил, что список слов - файл с словами, которые могут быть даже бессмысленными, но длины 3 или 4. Среди них есть палиндромы. И дальше по вопросу. Не понятны 2 вещи:
- Как лучше реализовать хэш-функцию, для палиндромов она должна давать одинаковые хэши независимо от того, реверсированная строка была подана или нет. Преподаватель привел в пример сумму аски-кодов, но такая хэш-функция совсем не устойчива к коллизиям...
- Как сделать поиск количества палиндромов из букв палиндрома (которые так же могут быть бессмысленными, но палиндромами.
Ответы (1 шт):
Реализовал искомую функцию хеширования PaliHash(str), чтобы она обладала нужными свойствами (хеш обратного порядка совпадает с хешем прямого) мы просто из двух строк прямой и обратной выбираем ту которая лексикографически меньше и хешируем её обычным хешем, благодаря выбору меньшей из строк мы автоматически реализуем это свойстово что прямой и обратный порядок даёт одинаковый хеш (подумайте почему).
В качестве обычного хеша для строки я использую std::hash, у него обычно (в популярных компиляторах) очень мало коллизий.
Далее, для второй задачи (подсчёта числа палиндромов для входных символов) я использовал std::next_permutation, эта функция позволяет перебрать все возможные перестановки букв, чтобы сгенерировать все возможные слова, сгенерировав все слова я считаю сколько из них обладают свойство палиндромности. Вывод программы в консоль указывает для каждого набора букв количество палиндромов, которое можно из них построить.
Саму проверку палиндромности я реализовал просто - реверсирую строку (используя RevStr(str) функцию, основанную на std::reverse) и если она совпала с исходной, то значит это палиндром, если нет, то не палиндром.
Для простоты я входные слова ни читал из файла, а задал список (вектор) в виде константы words.
#include <string>
#include <functional>
#include <iostream>
#include <algorithm>
#include <vector>
inline std::string RevStr(std::string s) {
std::reverse(s.begin(), s.end());
return s;
}
inline size_t PaliHash(std::string const & s) {
std::hash<std::string> hasher;
std::string rs = RevStr(s);
return s <= rs ? hasher(s) : hasher(rs);
}
int main() {
std::vector<std::string> words = {"aaa", "abc", "aba", "abcd", "abab"};
for (auto word: words) {
std::sort(word.begin(), word.end());
size_t pali_cnt = 0;
do {
if (word == RevStr(word))
++pali_cnt;
} while (std::next_permutation(word.begin(), word.end()));
std::cout << "'" << word << "': " << pali_cnt << ", ";
}
}
Вывод:
'aaa': 1, 'abc': 0, 'aab': 1, 'abcd': 0, 'aabb': 2,