How to work with string matrices?

Question

Programming

I can’t figure out how to check for each row of matrix A whether it is possible to get a sequence of characters written in the rows of matrix B by permuting its characters.

Answer 1

The simplest way is to sort each row of both matrices. Lines that were originally anagrams will match, and now you can find out what matches what. Complexity O(w (h _A +h _B )max{h _A +h _B , log w})
More complex (better asymptotic estimate). After each row has been sorted, the rows of matrix B are additionally reordered in lexicographic order (AAA < AAB <...< AAA < ABA). We use binary search to find matches. The complexity is O(w (h _A +h _B ) log max{w, h _A , h _B }).
You can also calculate the hashes for each row of the matrix B and store it in some data structure: the hash did not match anything - a full comparison is not carried out. Doesn't improve grades in the worst case, but improves on average.
Oftop. There was a case, I optimized Doom's WADs in size (the format allowed several blocks to refer to the same section of the file, and in many mods - and even in Doom itself - there were repetitions). I managed with hashing, and the hash was the size + a few bytes from the middle of the block.

Answer 2

Thank you!