Finding the longest word without these characters

Question

My goal is to go through the list of all English words (separated by '\n' characters) and find the longest word which doesn't have any of these characters: "gkmqvwxz". And I want to optimize it as much as possible. Here's what I came up with:

#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <unistd.h>


static inline int is_legal(size_t beg, size_t end, char* buffer) 
{
  static const char* bad = "gkmqvwxzio"; /* unwanted chars */
  for (; beg != end; ++beg) {            /* go through current word */
    char ch = tolower(buffer[beg]);      /* The char might be upper case */
    for (size_t j = 0; bad[j]; ++j)
      if (ch == bad[j])                  /* If it is found, return false */ 
        return 0;
  }

  return 1;                              /* else return true */
}

int main(void)
{
  char *buffer = NULL;                   /* contents of the text file */

  size_t length = 5000000;               /* maximum size */
  FILE* fp;
  fp = fopen("words.txt", "rb");

  if (fp) {
    fseek(fp, 0, SEEK_END);
    fseek(fp, 0, SEEK_SET);
    buffer = malloc(length);
    if (buffer) {
      fread(buffer, 1, length, fp);       /* read it all */
    }
    fclose(fp);
  }

  size_t beg = 0;                         /* current word boundaries */
  size_t end = 0;

  size_t mbeg = 0;                        /* result word */
  size_t mend = 0;

  while (buffer[end]) {
    beg = end++;

    for (; buffer[end] && buffer[end] != '\n'; ++end) /* read the next word */
      ; /* for loop doesn't have a body */

    if ((end - beg) > (mend - mbeg) && is_legal(beg, end, buffer)) { /* if it is a fit, save it */
      mbeg = beg;
      mend = end;
    }
  }

  printf("%.*s\n", mend - mbeg, buffer + mbeg);  /* print the output */ 
  return 0;
}

I read it all at once, then go through it with two indexes denoting beginning and ending of current word. When I find a word that fits, I save the corresponding indexes. Finally I print the output, which is "supertranscendentness". The output is correct, but I'd like to know:

1. If there's undefined behavior in my code
2. If there's a better way of doing this (without sacrificing performance)
3. If there's a way to improve the performance

Another point is the size_t length = 5000000; part. It is an estimated size of the string based of the file size.

Answer 1

The code is not bad as it stands, but I think there are some things that could be improved.

Think of the user

The input file name and unwanted letters are all hardcoded at the moment. It would be nice if the user could specify one or both of these parameters on the command line.

Add error handling

There is almost no error checking or handling. It's not hard to add, and it makes the program much more robust. Here's how the start of main might look:

int main(int argc, char *argv[]) {
    if (argc != 2) {
        puts("Usage: longword filename");
        return 0;
    }
    FILE* fp;
    fp = fopen(argv[1], "rb");

    if (!fp) {
        perror("couldn't open words file");
        return 3;
    }
    size_t length = 5000000;
    char *buffer = malloc(length);
    if (buffer == NULL) {
        perror("couldn't allocate memory");
        return 2;
    }
    length = fread(buffer, 1, length, fp);
    if (ferror(fp)) {
        perror("couldn't read file");
        free(buffer);
        return 1;
    }
    // rest of program here
    free(buffer);
}

Consider using standard library functions

At a very small performance penalty (as measured on my machine), one could write a very clean version using only standard functions:

char *longest = NULL;
int longestlen = 0;
char *word = strtok(buffer, "\n");
while (word) {
    const int len = strlen(word);
    if (len > longestlen) {
        if (strpbrk(word, "gkmqvwxzio") == NULL) { 
            longestlen = strlen(word);
            longest = word;
        }
    }
    word = strtok(NULL, "\n");
}
printf("%s\n", longest);

That is the way I'd probably write it unless there were some compelling reason that's not fast enough.

Use functions

Your is_legal function is not bad, but I'd also write a get_word_len function to fetch the length of the next word in the buffer.

static inline int get_word_len(const char *buff, const char *end) {
    int len = 0;
    for ( ; *buff != '\n' && buff < end; ++buff, ++len) 
    {}
    return len;
}

Use const where practical

The is_legal function doesn't alter the passed string, so that parameter should be const.

Think carefully about the problem

The current code might print the word followed by \n, but if the words doesn't happen to be the first in the file, it will also print the \n from the previous word. It's not necessarily wrong, but it's not consistent.

Use bool for boolean values

The implmentation of bool is in <stdbool.h> and should be used as the return type of is_legal.

Use only the required headers

In this program neither <stddef.h> nor <unistd.h> appear to be needed; I'd recommend omitting them and only including headers that are actually needed.

Consider using pointers

There may not be a performance difference in this case, but for problems like these, the use of pointers seems more natural to me. For example:

const char *end = buffer + length;
const char *longest = buffer;
int longestlen = 0;

for (const char *curr=buffer; curr < end;  ) {
    const int wordlen = get_word_len(curr, end);
    if (wordlen > longestlen) {
        if (is_good_word(curr, wordlen)) {
            longestlen = wordlen;
            longest = curr;
        }
    }
    curr += wordlen + 1;
}
printf("%.*s\n", longestlen, longest);

Here, is_good_word is like your is_legal function:

static inline bool is_good_word(const char *curr, int wordlen) {
  static const char* bad = "gkmqvwxzio";
  for ( ; wordlen; --wordlen) {
      char ch = tolower(*curr++);
      for (const char *badptr = bad; *badptr; ++badptr) {
          if (ch == *badptr) {
              return false;
          }
      }
  }
  return true;
}

Don't leak memory

The program allocates but does not free the buffer space. Yes, the operating system will clean up after you, but a free costs very little and allows for better memory leak checking with tools like valgrind.

Answer 2

Your code:

1. You only use things from 3 of the 6 includes. <string.h>, <stddef.h>, and <unistd.h> are superfluous, the last one just limiting portability.

2. is_legal() does not need to know about the bigger buffer. Just the sequence it should inspect is sufficient.

3. You assume everything works out perfectly fine:

   • The file can be opened for reading.
   • You succeed in allocating 5_000_000 bytes.
   • You can read all those Bytes from the file.

4. You fail to free the array you malloc()-ed. Not really a problem though, as the program terminates immediately afterwards.

5. If you allocate a fixed amount of memory on every run, why not just make it a static array?

6. return 0; is implicit for main() since C99.

Design limitations and considerations:

1. Consider using a smaller fixed buffer (size should be a power of 2, at least 32k or so), and scanning the file from start to end, instead of slurping it all in.

2. Consider allowing the user to override which characters are forbidden.

3. You are only handling single-byte character-sets. That might be enough, and it certainly simplifies things significantly.

4. Your code is almost certainly IO-bound, so the gains from optimising the algorithm are probably strictly limited. Still, consider a bit of pre-processing to cut out the more expensive calls.

   Specifically, prepare two bitfields character and whitespace, and use a simple lookup.

Answer 3

The fseek() calls in main() achieve nothing. They appear to be relicts of an attempt to measure file size that would look something like this (once the error checking has been added):

FILE *const fp = fopen("words.txt", "rb");
if (!fp) {
    perror("fopen");
    return 1;
}

if (fseek(fp, 0, SEEK_END)) {
    perror("fseek");
    return 1;
}
long length = ftell(fp);
if (length < 0) {
    perror("ftell");
    return 1;
}
if (fseek(fp, 0, SEEK_SET)) {
    perror("fseek");
    return 1;
}

char *const buffer = malloc(length+1);
if (!buffer) {
    fputs("malloc failed", stderr);
    return 1;
}
fread(buffer, 1, length, fp);       /* read it all */
fclose(fp);
buffer[length] = '\0';      /* add a string terminator */