Форум DL

Мой профиль

USACO 2006 Bebruary Bronze: Problem 13: Cow Phrasebook

USACO February 2006 Problem 'phrase' Analysis
by Bruce Merry and Rob Kolstad
The brute force approach is to take a message and try to match it to any of the phrase-book phrases. This will be too slow for the larger test cases. (Or at least it was supposed to be too slow: some brute-force solutions did succeed.)

A more efficient implementation uses a data structure called a hash table. This structure has similar properties to an array, but the lookup is done on a string or other object rather than an integer. All the prefixes of phrases are first inserted into the hash table. The messages are then looked up in the hash table to determine whether they are prefixes. This has the problem that the shortest phrases might not be detected properly.

A simple hash table would index simply on the first character of the answer. Test data with the first few characters always identical will defeat this.

This leaves half-interval search (MlogM + NlogM) as the preferred solution: read the phrasebook, sort it, then half-interval search for each of the input phrases. The trick is that half-interval search for an item not in the dictionary is slightly tricky to code correctly. Coach Rob's solution is below (not the shortest but potentially quite straightforward).

#include 
#include 
char phrases[55000][65];

chomp(char *p) {
    while (*p && *p != '\n')p++;
    *p = '\0';
}

cmp (a, b)
char *a, *b;
{
   while (*a && *b) {
	if (*a < *b) return -1;
	if (*a > *b) return 1;
	a++, b++;
   }
   if (*a) return 1;
   if (*b) return -1;
   return 0;
}

struct index_s *startchar[128];		/* chars are unsigned  */

prefix (p, q)
char *p, *q;
{
    for (; *p && *q; p++,q++)
	if (*p != *q) return 0;
    if (*p == '\0') return 1;
    return 0;
}


main () {
    FILE *fin = fopen ("phrase.in", "r");
    FILE *fout = fopen ("phrase.out", "w");
    char line[100];
    int i, m, n;
    int ntrue = 0;
    struct index_s *ind;

  /* read in the phrase book */
    fgets (line, 100, fin);
    sscanf(line, "%d %d", &m, &n);
    for (i = 0; i < m; i++)  {
	fgets (phrases[i], 65, fin);
	chomp (phrases[i]);
    }
    qsort(phrases, m, 65, cmp);

  /* check the phrases */
    for (i = 0; i < n; i++) {
	int ans, t, lo, hi, mid;
	fgets (line, 100, fin);
	chomp (line);
	lo = 0;
	hi = m-1;
	while (hi - lo > 0) {
	    mid = (lo + hi)/2;
	    t = cmp(line, phrases[mid]);
	    if (t > 0) { lo = mid+1; continue; }
	    if (t < 0) { hi = mid-1; continue; }
	    if (t == 0) { lo = hi = mid; break; }
	}
	if (prefix (line, phrases[lo]) || prefix(line, phrases[lo+1]) ) 
	    ntrue++;
    }
    fprintf (fout, "%d\n", ntrue);
    exit (0);
}