[UVA][Trie] 10975 - Dueue's Quiz＠Morris' Blog

2013-03-12 09:17:32| 人481| 回0 | 上一篇 | 下一篇

[UVA][Trie] 10975 - Dueue's Quiz

推 0 收藏 0 0 站台

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

hello

bye

one

two

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;
 nbsp; 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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
*/