Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1591
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1591
Grandma's Day
By Bruno Adami, Universidade de São Paulo - São Carlos 
Brazil
Timelimit: 1
Grandma is solving a word search puzzle. You really want to help her and will build an algorithm that, given the word search puzzle and the words to be searched, will print how many times each word appears.
In this puzzle, the words will be only in horizontal or vertical. The words do not wrap around. The words can also overlap the others, it is, the same letter in the puzzle may be used by more than one word. Count words with a single letter only once, see the first test case sample!
Input
The first line contains an integer T (T <= 100) indicating the number of test cases.
The first line of each test case will have two numbers, L (1 ≤ L ≤ 10* or 1 ≤ L ≤ 50**) and C (1 ≤ C ≤ 10* or 1 ≤ C ≤ 50**), the number of lines and columns of the word search puzzle respectively. The following L lines will have C lowercase letters of the English alphabet indicating the puzzle configuration. The next line there will be an integer P (1 ≤ P ≤ 50) indicating how many words there are to be searched. The following P lines contains the words that need to be searched. The words will have the limits accordingly to the size of the word search puzzle. The strings only contains lowercase letters of the English alphabet.
*for around 90% of the cases;
**for the other test cases.
Output
For each case, output for each word in a single line the number of times it appears in the word search puzzle, in the same order of the input. If the word is not found, print 0.
| Sample Input | Sample Output |
|
3 |
4 1 1 0 1 2 0 0 0 0 0 0 12 17 10 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int64;
char matrix[60][60];
int main()
{
ios::sync_with_stdio(false);
int t, l, c, x;
cin >> t;
while (t--) {
cin >> l >> c;
unordered_map < string, int> bib;
for (int i = 0; i < l; i++)
for (int j = 0; j < c; j++) {
cin >> matrix[i][j];
string temp = "";
temp += matrix[i][j];
if (bib.count(temp))
bib[temp]++;
else
bib.insert(mp(temp, 1));
}
for (int i = 0; i < l; i++) {
string s = "";
for (int j = 0; j < c; j++) {
s += matrix[i][j];
}
int tam = s.size();
for (int k = 2; k < = tam; k++) {
for (int h = 0; h < tam && h + k <= tam; h++) {
string temp = s.substr(h, k);
if (bib.count(temp))
bib[temp]++;
else
bib.insert(mp(temp, 1));
}
}
}
for (int j = 0; j < c; j++) {
string s = "";
for (int i = 0; i < l; i++) {
s += matrix[i][j];
}
int tam = s.size();
for (int k = 2; k < = tam; k++) {
for (int h = 0; h < tam && h + k <= tam; h++) {
string temp = s.substr(h, k);
if (bib.count(temp))
bib[temp]++;
else
bib.insert(mp(temp, 1));
}
}
}
cin >> x;
string pz;
while (x--) {
cin >> pz;
cout << bib[pz] << endl;
}
}
return 0;
}
Input
3 3
asa
bao
oab
6
a
asa
bao
boa
aob
ab
5 5
abcde
fghij
klmno
pqrst
uvwxy
6
agm
cdef
imq
ye
au
gfji
4 3
aaa
aaa
aaa
aaa
3
a
aa
aaa
Output
1
1
0
1
2
0
0
0
0
0
0
12
17
10