[zoj 2840] File Searching

File Searching

---

Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 161 Accepted Submit: 37

---

Have you ever used file searching tools provided by an operating system? For example, in DOS, if you type "dir *.exe", the OS will list all executable files with extension "exe" in the current directory. These days, you are so mad with the crappy operating system you are using and you decide to write an OS of your own. Of course, you want to implement file searching functionality in your OS.

Input:

The input contains several test cases. Consecutive test cases are separated by a blank line.

Each test case begins with an integer N (1 <= N < =100), the number of files in the current directory. Then N lines follow, each line has one string consisting of lowercase letters ('a'..'z') and the dot ('.') only, which is the name of a file. Then there is an integer M (1 <= M <= 20), the number of queries. M lines follow, each has one query string consisting of lowercase letters, the dot and the star ('*') character only. Note that the star character is the "universal matching character" which is used to represent zero or numbers of characters that are uncertain. In the beginning, you just want to write a simple version of file searching, so every string contains no more than 64 characters and there is one and only one star character in the query string.

Process to the End Of File (EOF).

Output:

For each test case, generate one line for the results of each query. Separate file names in the result by a comma (',') and a blank (' ') character. The file names in the result of one query should be listed according to the order they appear in the input. If there is no matching file, output "FILE NOT FOUND" (without the quotation) instead.

Separate two consecutive test cases with a blank line, but Do NOT output an extra blank line after the last one.

Sample Input:

4
command.com
msdos.sys
io.sys
config.sys
2
com*.com
*.sys

3
a.txt
b.txt
c.txt
1
*.doc

Sample Output:

command.com
msdos.sys, io.sys, config.sys

FILE NOT FOUND

Author: ZHOU, Yuan

---

Problem Source: Zhejiang University Local Contest 2007

这道题目就是我们决赛时候的一道诡异题目，我和菠菜一起讨论了几种测试用例，但是一直没有发现aaa和aa*aa这个特殊的用例，一直WA至最后一分钟。惨痛啊。回到寝室后把下午写的代码全部扔掉重来，重写代码，并且放弃使用STL，终于AC了。
基本思路就是star在中间，左边，右边和仅有一个star的情况分别讨论。代码不是很简洁，老大貌似有更精简的分类，不管了...

#include
#include

using namespace std;

char a[100][100];

#define NOT_FOUND "FILE NOT FOUND\n"

enum CMD {ALL = 1, LEFT, RIGHT, MID};
int main()
{
int n;
bool first = true;
while (scanf("%d", &n) != EOF)
{
if (!first)
printf("\n");
first = false;

int i = 0;
while (i < len =" i;" f =" true;" i =" 0;" size =" strlen(q);" size ="="" cmd =" ALL;" cmd =" LEFT;" i ="=""> 1)
cmd = RIGHT;
else
cmd = MID;
}
}

int star = i;
int j, k;

switch (cmd)
{
case ALL:
for (i = 0; i < f =" false;" i =" 0;" j =" strlen(a[i])" k =" size">= 0 && k > star; --j, --k)
{
if (q[k] != a[i][j])
break;
}
if (k == star)
{
if (!f)
printf(", ");
f = false;
printf("%s", a[i]);
}
}
if (f)
printf(NOT_FOUND);
else
printf("\n");
break;

case RIGHT:
for (i = 0; i < j =" 0," k =" 0;" k ="="" f =" false;" i =" 0;" j =" 0," k =" 0;" tmp =" j;" k ="="" j =" strlen(a[i])" k =" size"> star &&amp; j >= tmp; --j, --k)
{
if (q[k] != a[i][j])
break;
}
if (k == star)
{
if (!f)
printf(", ");
f = false;
printf("%s", a[i]);

}
}
}
if (f)
printf(NOT_FOUND);
else
printf("\n");
break;

default:
break;
}
}
}
return 0;
}