[POJ]1204 Word Puzzles

Word puzzles are usually simple and very entertaining for all ages. They are so entertaining that Pizza-Hut company started using table covers with word puzzles printed on them, possibly with the intent to minimise their client's perception of any possible delay in bringing them their order. 

Even though word puzzles may be entertaining to solve by hand, they may become boring when they get very large. Computers do not yet get bored in solving tasks, therefore we thought you could devise a program to speedup (hopefully!) solution finding in such puzzles. 

Your task is to produce a program that given the word puzzle and words to be found in the puzzle, determines, for each word, the position of the first letter and its orientation in the puzzle. 

You can assume that the left upper corner of the puzzle is the origin, (0,0). Furthemore, the orientation of the word is marked clockwise starting with letter A for north (note: there are 8 possible directions in total). 

首先我们可以对于每一个串去表里查找，但是显然这样时间复杂度太高了。我们需要转换思路，将其看做一道多串匹配的问题。多串匹配，自然就要用到AC自动机，我们可以根据输入的待匹配串建立AC自动机。在匹配的时候，我们在每个边界(第一行/列，最后一行/列)上的点，按照八个方向扫过去当做所有输入字符串。
这里有一个小的问题是，对于所有待匹配串，题目要求我们输出的是，在表里的起始位置和方向。方向很好解决，但是在我们匹配字符串的第一个字符时我们是不知道能否最终匹配的。我们当然可以在尾巴匹配的时候再向后回推回去，但是一个更好的解决办法是我们把所有待匹配串reverse之后再插入，这样当我们匹配到尾巴的时候正好是待匹配串在表中的起始位置，方向和当前的反一下即可。假设输入串有k个，平均长度为d，表的size 为m x n，那么建立AC自动机的时间复杂度为O(k * d)，匹配的时间复杂度为O(m * n)，代码如下：