C string algorithms

The concept

A C string is an array of char ended by a zero byte. Functions such as strlen simply walk the array until they find that zero, so they take O(n) time, and calling strlen in a loop condition repeats that work on every pass. strcmp compares two strings byte by byte and returns a negative, zero, or positive number.

A palindrome check uses two indexes that move toward each other from both ends, skipping characters that are not letters or digits and comparing the rest without regard to case. strstr finds the first occurrence of one string inside another. Calling it repeatedly from just after each match counts every occurrence, including overlapping ones if the search restarts one character after the previous match.

Code example

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

static size_t my_strlen(const char *s) {
  size_t n = 0;
  while (s[n] != '\0') {
    n++;
  }
  return n;
}

static int my_strcmp(const char *a, const char *b) {
  while (*a != '\0' && *a == *b) {
    a++;
    b++;
  }
  return (unsigned char)*a - (unsigned char)*b;
}

static int is_palindrome(const char *s) {
  int i = 0;
  int j = (int)strlen(s) - 1;
  while (i < j) {
    if (!isalnum((unsigned char)s[i])) {
      i++;
    } else if (!isalnum((unsigned char)s[j])) {
      j--;
    } else if (tolower((unsigned char)s[i]) != tolower((unsigned char)s[j])) {
      return 0;
    } else {
      i++;
      j--;
    }
  }
  return 1;
}

static int count_occurrences(const char *text, const char *pattern) {
  int count = 0;
  const char *p = text;
  while ((p = strstr(p, pattern)) != NULL) {
    count++;
    p++;
  }
  return count;
}

int main(void) {
  printf("%zu %zu\n", my_strlen("Programonic"), my_strlen(""));
  printf("%d %d\n", my_strcmp("apple", "apple") == 0, my_strcmp("apple", "banana") < 0);
  printf("%d %d\n", is_palindrome("A man, a plan, a canal: Panama"), is_palindrome("hello"));
  printf("%d\n", count_occurrences("abababa", "aba"));
  return 0;
}

11 0
1 1
1 0
3

Follow the code

Open the walkthrough to inspect the example one step at a time.

—

—

11 0

11 0
1 1

11 0
1 1

11 0
1 1
1 0

11 0
1 1
1 0

11 0
1 1
1 0
3

Behind the scenes

Cost and common mistakes

my_strlen and my_strcmp are O(n); count_occurrences is O(n·m) in the worst case.

• Calling strlen(s) in the condition of a loop over s makes the loop O(n²). Compute the length once.
• strcmp results should only be compared with 0, or tested for sign. Do not rely on the exact value.
• Passing a negative char to isalnum or tolower is undefined behaviour, so cast to unsigned char first.

Try it yourself

Why does the example print 1 for my_strcmp("apple", "apple") == 0?

Further reading

• C reference (cppreference) (external)
• C11 committee draft (N1570) (external)
• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) (external)