[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)，代码如下：

	//POJ 1204
	/*
	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).
	Input
	The first line of input consists of three positive numbers, the number of lines, 0 < L <= 1000, the number of columns, 0 < C <= 1000, and the number of words to be found, 0 < W <= 1000. The following L input lines, each one of size C characters, contain the word puzzle. Then at last the W words are input one per line.
	Output
	Your program should output, for each word (using the same order as the words were input) a triplet defining the coordinates, line and column, where the first letter of the word appears, followed by a letter indicating the orientation of the word according to the rules define above. Each value in the triplet must be separated by one space only.
	*/
	#include <cstdio>
	#include <cstring>
	#include <cstdlib>
	#include <vector>
	#include <algorithm>
	#include <cmath>
	#include <cctype>
	#include <iostream>
	#include <bitset>
	#include <queue>
	#include <climits>
	#include <string>
	using namespace std;
	const int INF = INT_MAX >> 1;
	const int MAXN = 1000 + 10;
	char s[MAXN][MAXN];
	int n, m, w;
	int dir[8][2] = {{0, 1}, {1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, {-1, 0}, {0, -1}};
	char ch[9] = "CEDFBHAG";
	int pos[MAXN][3];
	struct Node
	{
	Node* fail, *children[26];
	int id;
	Node()
	{
	fail = NULL;
	for(int i = 0; i < 26; ++i)
	children[i] = NULL;
	id = 0;
	}
	};
	//Aho–Corasick algorithm
	//AC automation
	class ACAutomaton
	{
	public:
	ACAutomaton()
	{
	root = new Node();
	}
	~ACAutomaton()
	{
	clear(root);
	}
	void insert(const string& str, int id)
	{
	Node* curr = root;
	int len = str.size();
	for(int i = 0; i < len; ++i)
	{
	char c = str[i];
	if(curr->children[c - 'A'] == NULL)
	curr->children[c - 'A'] = new Node();
	curr = curr->children[c - 'A'];
	}
	curr->id = id;
	}
	//build failed pointer for each node
	void buildFailed()
	{
	//for current node c with edge e, we look for its parent's fail pointer f
	//if f has the same char as e as its edge to chidlren c', we point c to c'
	//if not, we recursively look for f's parent until it is root
	queue<Node*> q;
	for(int i = 0; i < 26; ++i)
	{
	if(root->children[i])
	{
	q.push(root->children[i]);
	root->children[i]->fail = root;
	}
	}
	while(q.size())
	{
	Node* curr = q.front();
	q.pop();
	for(int i = 0; i < 26; ++i)
	{
	if(curr->children[i])
	{
	q.push(curr->children[i]);
	Node* fail = curr->fail;
	while(fail != root && !fail->children[i])
	fail = fail->fail;
	if(fail->children[i])
	curr->children[i]->fail = fail->children[i];
	else
	curr->children[i]->fail = root;
	}
	}
	}
	}
	void query(int i, int j, int d)
	{
	Node* curr = root;
	while(i >= 0 && i < n && j >= 0 && j < m)
	{
	char c = s[i][j];
	if(curr->children[c - 'A'])curr = curr->children[c - 'A'];
	else
	{
	while(curr && !curr->children[c - 'A'])
	curr = curr->fail;
	if(!curr)
	curr = root;
	else
	curr = curr->children[c - 'A'];
	}
	//we follow fail path to find all matches, since the substring we
	//are matching might contain a target word, for example: ACG, C
	//when we are matching AC and actually C is a target word which is on
	//failed path
	Node* helper = curr;
	while(helper != NULL)
	{
	if(helper->id)
	{
	int id = helper->id;
	pos[id][0] = i;
	pos[id][1] = j;
	pos[id][2] = 7 - d;
	}
	helper = helper->fail;
	}
	i += dir[d][0];
	j += dir[d][1];
	}
	}
	private:
	Node* root;
	void clear(Node* curr)
	{
	if(!curr)return;
	for(int i = 0; i < 26; ++i)
	clear(curr->children[i]);
	delete curr;
	}
	};
	int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	while (std::cin >> n >> m >> w) {
	for (int i = 0; i < n; ++i) std::cin >> s[i];
	ACAutomaton ac;
	for (int i = 1; i <= w; ++i)
	{
	string str;
	std::cin >> str;
	reverse(str.begin(), str.end());
	ac.insert(str, i);
	pos[i][0] = pos[i][1] = INF;
	}
	ac.buildFailed();
	for (int i = 0; i < n; ++i)
	{
	for(int k = 0; k < 8; ++k)
	{
	ac.query(i, 0, k);
	ac.query(i, m - 1, k);
	}
	}
	for (int i = 0; i < m; ++i)
	{
	for(int k = 0; k < 8; ++k)
	{
	ac.query(0, i, k);
	ac.query(n - 1, i, k);
	}
	}
	for (int i = 1; i <= w; ++i) std::cout << pos[i][0] << ' ' << pos[i][1] << ' ' << ch[pos[i][2]] << "\n";
	}
	return 0;
	}

view raw POJ_1204_Word Puzzles.cpp hosted with ❤ by GitHub