[UVA][Trie] 10975 - Dueue's Quiz
Problem L
Dueue’s Quiz
Hesam Dueue Bararie is the showman of a very popular TV quiz: “Bararian Nights”. In this quiz, there is a big table of letters with some words hidden in it among diagonal, vertical or horizontal directions. During the quiz, Dueue tells each one of the contestants a word and they must find the total number of occurrences of that word in the table.
Recently, Milk-Farhaad has decided to participate in this TV quiz and because cheating is permitted during this quiz (!), he wants you to help him by writing a computer program.
By the way, Milk-Farhaad has bought the whole dictionary and configurations of the table from Dueue. All he need is a computer program which calculates the total number of occurrences for each word of the dictionary in the table.
You can see one sample of this table in figure 1. All occurrences of the word “hello” are circled in that. Also, the total number of occurrences of the word “madam” is equal to 2 because it must be counted twice: one from left to right and the other one from right to left.
Figure 1. Dueue’s Table
The Input
The
first line of the input file is an integer 
which is the number of test cases. The first line of each
test case is an integer 
which is the number of
words in the dictionary that should be used for this test case. After that, comes D lines each of which containing a word, having
length of no more than 1000 characters, in the dictionary. Words are all
constructed from lowercase letters: a…z.
Then,
comes a line containing an integer 
, the total number of queries for the test case. For each
query, there will be two integers
which are the number of rows and the number of columns of the
table respectively. Next, there are M lines each one containing N
characters representing the configuration of each table of the quiz.
The Output
For each test case, your program should write a line with the phrase “Test Case #i” in which i is the index of the current test case starting from 1. Then comes the answer for each query in that test case. The answer to each query starts with a line containing the phrase “Query #j”. Then, all the words from dictionary which actually occurred in the table of that query should be listed one in each line (or each in one line!) together with their total number of occurrences in the given table. These words must be sorted in alphabetical order. There should be an empty line after the output for each test case.
Sample Input
1
4
hello
bye
one
two
2
3 3
bye
okk
res
3 3
one
wzq
too
Sample Output
Test Case #1
Query #1
bye 1
Query #2
one 1
two 1
Amirkabir University of Technology - Local Contest - Round #2
用內存池加快速度，不使用動態記憶體配置。
建一棵 keyword tree (Trie)，嘗試所有字串可能，去搜尋整個 Trie，遇到哪些節點就記錄哪些單字出現過。
用 AC automation 效果並不好，原因是樹似乎有點稀疏。
Trie 0.232 s
AC automation 2.308 s
// 0.232 s
#include <stdio.h>
#include <string.h>
#include <map>
#include <iostream>
#include <algorithm>
#define rename(c) (c-'a')
using namespace std;
struct Node {
Node *next[26];
int label; // which word end.
void init() {
label = -1;
memset(next, 0, sizeof(next));
}
};
Node BUF[650000];
int BUFsize;
int insert_Trie(char str[], Node *root, int label) {
static Node *p;
static int i, idx;
p = root;
for(i = 0; str[i]; i++) {
idx = rename(str[i]);
if(p->next[idx] == NULL) {
BUFsize++;
BUF[BUFsize].init();
p->next[idx] = &BUF[BUFsize];
}
p = p->next[idx];
}
if(p->label < 0) {
p->label = label;
return 1;
}
return 0;
}
char T[15000][1005], g[105][105];
int D[][2] = {{0,1},{1,0},{-1,0},{0,-1},
{1,1},{1,-1},{-1,1},{-1,-1}};
int main() {
int t, cases = 0;
scanf("%d", &t);
getchar();
int n, q, i, j, k;
while(t--) {
scanf("%d", &n);
BUFsize = 0;
BUF[BUFsize].init();
Node *root = &BUF[BUFsize];
Node *p;
while(getchar() != '\n');
for(i = 0, j = 0; i < n; i++) { // offline process
gets(T[j]);
j += insert_Trie(T[j], root, j);
}
n = j;
scanf("%d", &q);
printf("Test Case #%d\n", ++cases);
int a, b, x, y, dir, idx, qcases = 0;
while(q--) {
printf("Query #%d\n", ++qcases);
scanf("%d %d", &a, &b);
while(getchar() != '\n');
for(i = 0; i < a; i++)
gets(g[i]);
int cnt_mark[15000] = {};
map<string, int> output;
for(i = 0; i < a; i++) {
for(j = 0; j < b; j++) {
for(dir = 0; dir < 8; dir++) {
p = root;
x = i, y = j;
while(p != NULL && x < a && x >= 0 && y < b && y >= 0) {
idx = rename(g[x][y]);
if(p->next[idx] == NULL)
break;
p = p->next[idx];
if(p->label >= 0)
cnt_mark[p->label]++;
x += D[dir][0], y += D[dir][1];
}
}
}
}
for(i = 0; i < n; i++)
if(cnt_mark[i])
output[T[i]] = cnt_mark[i];
for(map<string, int>::iterator it = output.begin();
it != output.end(); it++)
printf("%s %d\n", (it->first).c_str(), it->second);
}
puts("");
}
return 0;
}
附錄 AC automation 的做法
//2.308 s
#include <stdio.h>
#include <string.h>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
#define rename(c) (c-'a')
using namespace std;
struct Node {
Node *next[26], *fail;
int label; // which word end.
/*Node() {
label = -1;
memset(next, 0, sizeof(next));
}*/
void init() {
label = -1;
fail = NULL;
memset(next, 0, sizeof(next));
}
};
Node BUF[625000];
int BUFsize;
void insert_Trie(char str[], Node *root, int label) {
static Node *p;
static int i, idx;
p = root;
for(i = 0; str[i]; i++) {
idx = rename(str[i]);
if(p->next[idx] == NULL) {
//p->next[idx] = new Node();
BUFsize++;
BUF[BUFsize].init();
p->next[idx] = &BUF[BUFsize];
}
p = p->next[idx];
}
p->label = label;
}
void build_ACautomation(Node *root) {
queue<Node*> Q;
Node *nd, *p;
root->fail = NULL;
Q.push(root);
while(!Q.empty()) {
nd = Q.front(), Q.pop();
for(int i = 0; i < 26; i++) {
if(nd->next[i] == NULL)
continue;
Q.push(nd->next[i]);
p = nd->fail;
while(p != NULL && p->next[i] == NULL)
p = p->fail;
if(p == NULL)
nd->next[i]->fail = root;
else
nd->next[i]->fail = p->next[i];
}
}
}
void query_ACautonmation(char *str, Node *root, int *exist_mark) {
static Node *p, *q;
static int i, idx;
p = root;
for(i = 0; str[i]; i++) {
idx = rename(str[i]);
while(p != root && p->next[idx] == NULL)
p = p->fail;
p = p->next[idx];
p = (p == NULL) ? root : p;
q = p;
while(q != root) {
exist_mark[q->label]++;
q = q->fail;
}
}
}
void free_Trie(Node *root) {
queue<Node*> Q;
Node *nd;
while(!Q.empty()) {
nd = Q.front(), Q.pop();
for(int i = 0; i < 26; i++) {
if(nd->next[i] != NULL)
Q.push(nd->next[i]);
}
delete nd;
}
}
char T[15000][1005], g[105][105], S[1024];
int main() {
int t, cases = 0;
scanf("%d", &t);
getchar();
int n, q, i, j, k;
while(t--) {
scanf("%d", &n);
BUFsize = 0;
BUF[BUFsize].init();
//Node *root = new Node();
Node *root = &BUF[BUFsize];
Node *p;
while(getchar() != '\n');
for(i = 0; i < n; i++) { // offline process
gets(T[i]);
insert_Trie(T[i], root, i);
}
scanf("%d", &q);
printf("Test Case #%d\n", ++cases);
int a, b, x, y, dir, idx, qcases = 0;
while(q--) {
printf("Query #%d\n", ++qcases);
scanf("%d %d", &a, &b);
while(getchar() != '\n');
for(i = 0; i < a; i++)
gets(g[i]);
build_ACautomation(root);
int cnt_mark[15000] = {};
map<string, int> output;
int idx;
for(i = 0; i < a; i++) { // row left-right
p = root;
x = i, y = 0, idx = 0;
while(x < a && x >= 0 && y < b && y >= 0) {
S[idx++] = g[x][y];
y++;
}
S[idx] = '\0';
query_ACautonmation(S, root, cnt_mark);
}
for(i = 0; i < a; i++) { // row right-left
p = root;
x = i, y = b-1, idx = 0;
while(x < a && x >= 0 && y < b && y >= 0) {
S[idx++] = g[x][y];
y--;
}
S[idx] = '\0';
query_ACautonmation(S, root, cnt_mark);
}
for(i = 0; i < b; i++) { // column left-right
p = root;
x = 0, y = i, idx = 0;
while(x < a && x >= 0 && y < b && y >= 0) {
S[idx++] = g[x][y];
x++;
}
S[idx] = '\0';
query_ACautonmation(S, root, cnt_mark);
}
for(i = 0; i < b; i++) { // column right-left
p = root;
x = a-1, y = i, idx = 0;
while(x < a && x >= 0 && y < b && y >= 0) {
S[idx++] = g[x][y];
x--;
}
S[idx] = '\0';
query_ACautonmation(S, root, cnt_mark);
}
for(i = 0; i < a; i++) { // slide down
p = root;
x = i, y = 0, idx = 0;
while(x < a && x >= 0 && y < b && y >= 0) {
S[idx++] = g[x][y];
x++, y++;
}
S[idx] = '\0';
query_ACautonmation(S, root, cnt_mark);
for(j = 0, k = idx-1; j < k; j++, k--)
swap(S[j], S[k]);
query_ACautonmation(S, root, cnt_mark);
}
for(i = 1; i < b; i++) { // slide down
p = root;
x = 0, y = i, idx = 0;
while(x < a && x >= 0 && y < b && y >= 0) {
S[idx++] = g[x][y];
x++, y++;
}
S[idx] = '\0';
query_ACautonmation(S, root, cnt_mark);
for(j = 0, k = idx-1; j < k; j++, k--)
swap(S[j], S[k]);
query_ACautonmation(S, root, cnt_mark);
}
for(i = 0; i < a; i++) { // slide up
p = root;
x = i, y = 0, idx = 0;
while(x < a && x >= 0 && y < b && y >= 0) {
S[idx++] = g[x][y];
x--, y++;
}
S[idx] = '\0';
query_ACautonmation(S, root, cnt_mark);
for(j = 0, k = idx-1; j < k; j++, k--)
swap(S[j], S[k]);
query_ACautonmation(S, root, cnt_mark);
}
for(i = 1; i < b; i++) { // slide up
p = root;
x = a-1, y = i, idx = 0;
while(x < a && x >= 0 && y < b && y >= 0) {
S[idx++] = g[x][y];
x--, y++;
}
S[idx] = '\0';
query_ACautonmation(S, root, cnt_mark);
for(j = 0, k = idx-1; j < k; j++, k--)
swap(S[j], S[k]);
query_ACautonmation(S, root, cnt_mark);
}
for(i = 0; i < n; i++)
if(cnt_mark[i])
output[T[i]] = cnt_mark[i];
for(map<string, int>::iterator it = output.begin();
it != output.end(); it++)
printf("%s %d\n", (it->first).c_str(), it->second);
}
puts("");
//free_Trie(root);
}
return 0;
}
/*
1
1
a
1
1 1
a
*/