gistfile1.c

#include <ctype.h>
#include <stdio.h>
#include <string.h>

static int match(const char *query, const char *username);
static void do_search(const char *query, char **usernames, int ulen);
static int lex_smaller(const char *a, const char *b);
 
void typeahead(char **usernames, int usernames_length, char **queries, int queries_length) {
  int i;

   for (i=0; i<queries_length; i++)
        do_search(queries[i], usernames, usernames_length);
}

static void do_search(const char *query, char **usernames, int ulen) {
    const char *max_u = NULL;
    int i, max_common = 0, common;

    for (i=0; i<ulen; i++) {
        common = match(query, usernames[i]);
        if (common && common >= max_common) {
            if (!max_u ||
                (max_u && lex_smaller(usernames[i], max_u))) {
              max_common = common;
              max_u = usernames[i];
            }
        }
    }
    if (!max_common)
        printf("-1\n");
    else
        printf("%s\n", max_u);
}

static int match(const char *query, const char *username) {
    int i=0;
    int qlen = strlen(query);
    int ulen = strlen(username);
    
    while (i < qlen && i < ulen &&
           tolower(query[i]) == tolower(username[i]))
        i++;
    return i == qlen ? i : 0;
}
                
static int lex_smaller(const char *a, const char *b) {
    int alen = strlen(a);
    int blen = strlen(b);
    int i=0;
    
    while (i<alen && i<blen && a[i] == b[i]) i++;
    
    if (i == alen)
        return 1;
    else if (i == blen)
        return 0;
    return tolower(a[i]) <= tolower(b[i]);
}