alv-r-'s blog

Help with Aho-Corasick Problem
By alv-r-, 10 years ago, In English

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!

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

"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.

1

1 5 3
ABCBA
C
BCB
ABCBA

It causes a lot of possible output.

And what about the following input?

1

1 1 1
A
A

Is it valid?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :(

    → Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

It seems your program fails on this test:

1
1 3
2  
ABC
ABC
CBA
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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! :)

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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).

    → Reply