How can I find length of longest word in const char string without using auxiliary string?

#include <stdio.h>

int longest(const char *str) {
    int max = 0, prev = 0, final_max = 0;
    
    while (*str != '\0') {
        prev = max;
        max = 0;
    
        while (1) {
            if (*str != ' ') 
                max  ;

            str  ;

            if (*str == ' ') 
                break;
        }
    
        if (prev > max)
            final_max = prev;
    
        str  ;
  }

  return final_max;
}

void main() {
    const char str[] = "Longest word in string";
    printf("%d", longest(str));
}

This prints 4 as length of longest word. Could you help me fix this?

CodePudding user response：

You can find the longest word in linear time. This is surely optimal since any algorithm has to process every character at least once.

The basic idea is to loop over every character of the string, keeping track of the position of the last space (or any other word separator). Everytime the current character is a space we update the answer.

Note that we need to add an extra check at the end for the case where the longest word is the last in the string (and thus is not necessarily followed by a space).

Here's a simple implementation:

#include <stdio.h>

size_t longest(const char *str) {
  size_t i, last=-1, ans=0;
  for (i = 0; str[i] != '\0'; i  )
    if (str[i] == ' ') {
      if (ans < i-last) ans = i-last-1;
      last = i;
    }
  if (ans < i-last) ans = i-last-1;
  return ans;
}

void main(){
  printf("%zu\n", longest("Longest word in string")); // 7
}

CodePudding user response：

Simply walk the string once.

After walking past white spaces, note the beginning of a word. After walking through a word, note its length and compare to the current longest length. Do this until a null character detected.

Use size_t, rather than int to handle long strings.

Access the characters via an unsigned char* to properly use isspace().

Example:

#include <stdio.h>
#include <stdlib.h>

size_t longest1(const char *str) {
  // Print up to 30 characters of str - for debug
  printf("<%.30s> ", str);

  size_t longest_length = 0;
  // Access the string as if it had unsigned chars.
  const unsigned char *s = (const unsigned char*) str;

  while (isspace(*s)) {
    s  ;
  }

  while (*s) {
    const unsigned char *start = s;
    do {
      s  ;
    } while (!isspace(*s) && *s);
    size_t length = (size_t) (s - start);
    if (length > longest_length) {
      longest_length = length;
    }
    while (isspace(*s)) {
      s  ;
    }
  }
  return longest_length;
}

Tests

int main(void) {
  printf("%zu\n", longest("Longest word in string"));
  printf("%zu\n", longest(""));
  printf("%zu\n", longest(" "));
  printf("%zu\n", longest("  "));
  printf("%zu\n", longest("a"));
  printf("%zu\n", longest(" b"));
  printf("%zu\n", longest("c "));
  printf("%zu\n", longest("dd e"));
  printf("%zu\n", longest(" ff g"));
  printf("%zu\n", longest("hh i "));
  printf("%zu\n", longest("j kk"));
  printf("%zu\n", longest(" l mm"));
  printf("%zu\n", longest("n oo "));
  char *buf = malloc(INT_MAX * 2u);
  if (1 && buf) {
    memset(buf, 'x', INT_MAX * 2u - 1);
    buf[INT_MAX * 2u - 1] = '\0';
    printf("%zu\n", longest(buf));
    free(buf);
  }
}

Output

<Longest word in string> 7
<> 0
< > 0
<  > 0
<a> 1
< b> 1
<c > 1
<dd e> 2
< ff g> 2
<hh i > 2
<j kk> 2
< l mm> 2
<n oo > 2
<xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> 4294967293