Hi, I've being trying to solve this problem on SPOJ: http://www.spoj.com/problems/WPUZZLES/ (which I've seen in many places as a recommended Aho-Corasick problem).
I'm currently getting WA on it and can't figure out why, could someone please help giving me a hint about what is wrong? (Or maybe giving me some test cases where it fails).
My current code is this: http://pastebin.com/vzLNwKk6 The aho-corasick part is based on this implementation: https://gist.github.com/andmej/1233426
My idea is: put both the word and its reverse on keywords[], then run on the matching machine with each line of the puzzle. I'm currently running 2 directions at a time in the loop (4 with the reverses). Directions 'A', 'C', 'E', 'G' in one and the remaining in another.
As far as I can tell, a matching is missing when the code is printing the answer, have no idea under what circumstances this happens though.
Any help is appreciated!
"You can assume that each word can be found exactly once in the word puzzle."
I don't know if test data contains following input.
It causes a lot of possible output.
And what about the following input?
Is it valid?
I thought about that, the problem doesn't specify how you should print in case of palindromes (because you can have two possible answers for them).
So my guess is that "You can assume that each word can be found exactly once in the word puzzle" applies for this case (no anagrams, since you could find them twice, depending on interpretation).
I tried to change the search order in a way that would print the "first" match (meaning the one with smaller i and j for its coordinates), still WA :(
It seems your program fails on this test:
That was exactly the problem, when checking isrev["CBA"], for example, I would consider it a reverse string and add the result for "ABC", ignoring that "CBA" is also there.
Fixed, got AC, thanks a lot! :)
Can someone explain the solution? I am familiar with Aho-Corasick, but I can not figure out how to apply it here. Thanks in advance!
You can consider the puzzle to be a collection of texts, while the words to be found are the keywords. By a collection of texts I mean that each row, column or diagonal (+ the inverse of each) is a text.
So, if you build a matching automaton (using aho corasick) with the keywords, you can run each 'text' on it and see what keywords are in there in O(n) (n = length of the text).
What I did was consider both the actual word and its inverse as keywords, so you can run only the 'texts' in a single direction and find the ones that would be a match for its reversed counterpart. (Cause you are also guaranteed that each word appears only once). Then I match 2 directions (4 counting the reversed ones) at a time, using the same iteration, but keeping two different 'currentStates'. (In short: only two matrix iterations for all the 8 directions).
As far as I've seen, on these 2d matching problems you can usually use just some sort of complete search with backtracking, but in this case (1000x1000 board, 1000 length keywords) this is too slow, hence the need for aho corasick (I've also seen someone else do it with rabin-karp).
thank you very much, alv-r-