UVa 10975

From Algorithmist
Jump to navigation Jump to search

10975 - Dueue's Quiz[edit]

http://uva.onlinejudge.org/external/109/10975.html

Summary[edit]

Given a dictionary and rectangular array of letters, count the occurences of each word from the dictionary in it in all possible orientations.

Explanation[edit]

One easy way to solve the problem is to store the words of the dictionary in a trie. Then, for every starting position and orientation, simply traverse the trie, counting the occurences of each word.

A word may appear more than once in the dictionary. In this case, its repetitions should be ignored.

Input[edit]

2
4
hello
bye
one
two
2
3 3
bye
okk
res
3 3
one
wzq
too
5
madam
madam
hello
e
ll
1
6 8
xhellohx
xoezxecx
xlnllbvx
xlmllasx
xeogfodx
xhmadamx

Output[edit]

Test Case #1
Query #1
bye 1
Query #2
one 1
two 1

Test Case #2
Query #1
e 32
hello 4
ll 16
madam 2