|
|
这题基本上没有算法，只用了一个字符串的hash。
但代码很长，200+行。非常荣幸的1ac了！
 #include <stdio.h>
#include <string.h>
#define MAX_LINES 2048
#define MAX_LINE_LEN 128
#define MAX_DOCS 128
#define MAX_WORDS 65536
#define MAX_WORDS_PER_LINE 128
  struct node  {
 int doc, line;
struct node *next;
 };
char lines[MAX_LINES][MAX_LINE_LEN];
int docs[MAX_DOCS][MAX_LINES];
int docs_cnt;
unsigned int occur[MAX_DOCS][(MAX_WORDS + 31) / 32];
unsigned int hash[MAX_WORDS];
struct node nodes[MAX_WORDS], *head[MAX_WORDS], *tail[MAX_WORDS];
int nodes_cnt;
inline unsigned int strhash(char *str, int len)
{
unsigned int h = 0;
  while (len--) {
h *= 31;
if (*str >= 'A' && *str <= 'Z')
h += *str - 'A' + 'a';
else
h += *str;
str++;
 }
return h;
}
inline unsigned int test_bit(unsigned int *arr, int idx)
{
return arr[idx >> 5] & (1 << (idx & 0x1f));
}
inline void set_bit(unsigned int *arr, int idx)
{
arr[idx >> 5] |= 1 << (idx & 0x1f);
}
inline int is_alpha(char ch)
{
return ch >= 'a' && ch <= 'z' ||
ch >= 'A' && ch <= 'Z'
;
}
inline int split(char *line, char **strs, int *lens)
{
int cnt = 0;
while (*line) {
while (*line && !is_alpha(*line))
line++;
if (!*line)
break;
*strs++ = line;
for (*lens = 0; is_alpha(*line); (*lens)++)
line++;
lens++;
cnt++;
}
return cnt;
}
inline int find(unsigned int h)
{
int i = h % MAX_WORDS;
while (hash[i] && hash[i] != h)
i = (i + 1) % MAX_WORDS;
return i;
}
inline void insert(char *str, int len, int doc, int line)
{
unsigned int h = strhash(str, len);
int i = find(h);
struct node *t = &nodes[nodes_cnt++];
hash[i] = h;
t->doc = doc;
t->line = line;
if (!head[i])
head[i] = t;
else
tail[i]->next = t;
tail[i] = t;
set_bit(occur[doc], i);
}
int output_cnt, last_doc;
inline void output(int doc, int line)
{
if (last_doc == -1)
last_doc = doc;
if (last_doc != doc) {
printf("----------\n");
last_doc = doc;
}
printf("%s\n", lines[docs[doc][line]]);
output_cnt++;
}
struct node *list[MAX_LINES];
inline void mark_one(int id, int doc)
{
struct node *t;
for (t = head[id]; t; t = t->next)
if (doc == -1 || t->doc == doc)
list[docs[t->doc][t->line]] = t;
}
inline void dump_list()
{
int i;
for (i = 0; i < MAX_LINES; i++)
if (list[i])
output(list[i]->doc, list[i]->line);
}
inline void search_one(int id)
{
memset(list, 0, sizeof(list));
mark_one(id, -1);
dump_list();
}
inline void search_and(int id1, int id2)
{
int i;
memset(list, 0, sizeof(list));
for (i = 0; i < docs_cnt; i++)
if (test_bit(occur[i], id1) && test_bit(occur[i], id2)) {
mark_one(id1, i);
mark_one(id2, i);
}
dump_list();
}
inline void search_or(int id1, int id2)
{
memset(list, 0, sizeof(list));
mark_one(id1, -1);
mark_one(id2, -1);
dump_list();
}
inline void search_not(int id)
{
int i, j;
for (i = 0; i < docs_cnt; i++)
if (!test_bit(occur[i], id))
for (j = 0; docs[i][j]; j++)
output(i, j);
}
int main()
{
int i, j, k, c, n, l = 1, lens[MAX_WORDS_PER_LINE], id[8];
char *strs[MAX_WORDS_PER_LINE];
freopen("e:\\in.txt", "r", stdin);
scanf("%d\n", &docs_cnt);
for (i = 0; i < docs_cnt; i++) {
for (j = 0;
gets(lines[l]), strcmp(lines[l], "**********");
j++, l++)
{
docs[i][j] = l;
c = split(lines[l], strs, lens);
for (k = 0; k < c; k++)
insert(strs[k], lens[k], i, j);
}
}
scanf("%d\n", &n);
while (n--) {
gets(lines[l]);
c = split(lines[l], strs, lens);
output_cnt = 0;
last_doc = -1;
for (i = 0; i < c; i++)
id[i] = find(strhash(strs[i], lens[i]));
if (c == 1)
search_one(id[0]);
else if (c == 2)
search_not(id[1]);
else if (strs[1][0] == 'A')
search_and(id[0], id[2]);
else
search_or(id[0], id[2]);
if (!output_cnt)
printf("Sorry, I found nothing.\n");
printf("==========\n");
}
return 0;
}
|