Как работать со строковыми матрицами?

Question

[Bogdan1111]

Не могу понять, как проверить для каждой строки матрицы А, можно ли перестановкой ее символов получить последовательность символ, записанных в строках матрицы B.

Comments

[Alexej Simakov]

Проблема в проверке является ли одна строка анаграммой другой строки или в работе с матрицей?

Answer 1

[Mercury13]

Простейший способ — отсортировать каждую строку обеих матриц. Строки, изначально являвшиеся анаграммами, будут совпадать, и теперь уже можно выяснять, что с чем совпадает. Сложность O(w·(h_A+h_B)·max{h_A+h_B, log w})

Более сложный (лучше асимптотическая оценка). После того, как отсортировали каждую строку, строки матрицы B дополнительно переупорядочиваем в лексикографическом порядке (ААА < ААБ <…< ААЯ < АБА). Для поиска совпадений пользуемся двоичным поиском. Сложность O(w·(h_A+h_B)·log max{w, h_A, h_B}).

Можно также каждой строчке матрицы B посчитать хэши и запомнить в какой-то структуре данных: хэш не совпал ни с чем — полное сравнение не проводится. Не улучшает оценки в худшем случае, но улучшает в среднем.

Офтоп. Было дело, я оптимизировал WAD’ы Doom’а по размеру (формат позволял нескольким блокам ссылаться на один и тот же участок файла, а во многих модах — и даже в самом Doom’е — были повторы). Обошёлся хэшированием, и хэшем был размер + несколько байт из середины блока.

Answer 2

[Bogdan1111]

Спасибо!

Comments

[AtomKrieg]

Спасибо на рейтинг не намажешь. Надо помечать ответы, как решения

[Mercury13]

Если оно работает — пометьте, пожалуйста, ответ как решение.