C string algorithms
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.
C
#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;
}