Word Puzzles

WPUZZLES
I spent a good 5 hours of nonstop coding solving this problem. You simply have to search every row, column, and diagonal (plus backwards!) in order to find each word – there is no other way that I can think of, especially if the grid is randomized.

The problem is TLE. A simple analysis should convince you that using the naive method of O(nk) string search takes too many operations. Now what?

You could try using KMP or Boyer-Moore. The problem is that each of these algorithms must be run separately every time that you are trying to find one string in another – and since the haystack is much larger than the needle in each case, this, too, was too slow. Blue Mary writes in the forums that he solved this problem using a trie graph (supposedly a DAWG) and the extended KMP algorithm. The extended KMP algorithm, presumably, would allow multiple pattern matching without incurring a cost in time proportional to the length of the haystack multiple times. However, I could not find any online resources pertaining to this; they would probably be too complicated anyways.

The optimal solution is to use the Aho-Corasick algorithm. Since each word can be found only once in the puzzle, the expected running time is linear. This is rather complex, and similar to building a suffix tree of the input string (which allows searching in time proportional to the needle’s length.) This would be quite a challenge to code – for me, at least.

The algorithm to use here is Rabin-Karp. Each word can be found only once, so we don’t necessarily incur multiple times the cost of verifying that the search string is actually found. Also, the use of a hash table makes the overall complexity linear (assuming perfect hashing.) My solution then runs in 2.49s using scanf, compared with 2.69s for an implementation of Aho-Corasick (user “smoke”) – although maybe he used cin, I don’t know for sure.