Handwritten code

  1. String API
  2. strlen
  3. strcpy
  4. strstr
  5. atoi
  6. Substring lookup
  7. KMP
  8. Boyer-Moore
  9. Rabin-Karp
  10. Stack and Queue
  11. Hannota

String API

strlen

1
2
3
4
5
size_t strlen(const char* str) {
const char* s = str;
while(*s) { ++s; }
return s - str;
}

strcpy

1
2
3
4
5
6
char* strcpy(char* to, const char* from) {
assert(to != NULL && from != NULL);
char* p = to;
while (*p++ = *from++);
return to;
}

strstr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char *strstr(const char *haystack, const char *needle) {
// if needle is empty return the full string
if (!*needle) return (char*) haystack;
const char *p1;
const char *p2;
const char *p1_advance = haystack;
for (p2 = &needle[1]; *p2; ++p2) {
p1_advance++; // advance p1_advance M-1 times
}
for (p1 = haystack; *p1_advance; p1_advance++) {
char *p1_old = (char*) p1;
p2 = needle;
while (*p1 && *p2 && *p1 == *p2) {
p1++; p2++;
}
if (!*p2) return p1_old;
p1 = p1_old + 1;
}
return NULL;
}

atoi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int atoi(const char *str) { 
int num = 0;
int sign = 1;
const int len = strlen(str);
int i = 0;
while (str[i] == ' ' && i < len) ++i;

if (str[i] == '+') ++i;
if (str[i] == '-') { sign = -1; ++i; }

for (; i < len; ++i) {
if (str[i] < '0' || str[i] > '9') break;
if (num > INT_MAX / 10 ||
num == INT_MAX / 10 &&
(str[i] - '0') > INT_MAX % 10) {
return sign == -1 ? INT_MIN : INT_MAX;
}
num = num * 10 + str[i] - '0';
}
return num * sign;
}

Substring lookup

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void compute_prefix(const char *pattern, int next[]) { 
int i;
int j = -1;
const int m = strlen(pattern);
next[0] = j;
for (i = 1; i < m; i++) {
while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j];
if (pattern[i] == pattern[j + 1]) j++;
next[i] = j;
}
}


int kmp(const char *text, const char *pattern) {
int j = -1;
const int n = strlen(text);
const int m = strlen(pattern);
if (n == 0 && m == 0) return 0; /* "","" */
if (m == 0) return 0; /* "a","" */
int *next = (int*)malloc(sizeof(int) * m);
compute_prefix(pattern, next);
for (int i = 0; i < n; i++) {
while (j > -1 && pattern[j + 1] != text[i]) j = next[j];
if (text[i] == pattern[j + 1]) j++;
if (j == m - 1) {
free(next);
return i-j;
}
}
free(next);
return -1;
}

Boyer-Moore

Rabin-Karp

Stack and Queue

Hannota

1
2
3
4
5
6
7
8
9
void hanoi(int n, char x, char y, char z) { 
if(n == 1) {
printf("%d from %c to %c\n", n, x, z); return;
} else {
hanoi(n-1, x, z, y);
printf("%d from %c to %c\n", n, x, z);
hanoi(n-1, y, x, z);
}
}
script>