Strings: Concatenation

A common operation with strings is appending one string to another. After you figured out copying, you should be able to figure this out too: first, we need to find the end of the first string, and then start copying the second string into it, character by character. This function is called strcat in string.h, and it returns the pointer to the first string (the one we append to), in a similar fashion to how the value of a += b is the assigned value, i.e. the new value of a.

So, let's implement strcat:

#include <stdio.h>

char *strcat(char *where, char *what) {
  /* TODO: your code here */

  return where;
}

int main() {
  /* Test code, do not change */
  char s[100] = { 0 };
  char *s1, s2, s3;
  s1 = strcat(s, "first ");
  s2 = strcat(s, "second ");
  s3 = strcat(s, "third");
  printf("<%s> %d %d %d\n", s, s1 == s, s2 == s, s3 == s);
  return 0;
}

Similar to how I mentioned it with the string copy (strcpy) function, there's a "classic C" way of writing strcat too. You don't need to write it like this always, but it's worth understanding how that works. Check the previous page on strcpy if it's unclear, because the following code for strcat is very similar:

while (*where)
  ++where;  /* iterate till the end of the first string */

while (*where++ = *what++)
  ;  /* copy character by character

Same as before, since you need to return the initial value of where, you will need to save it in a variable before you start moving the pointer.

There is one more interesting thing to discuss related to strcat, which brings us back to the topic of time complexity. Imagine the following code:

char s[1000] = { 0 };  /* allocate enough memory */
for (int i = 0; i < N; ++i) {
	strcat(s, "a");
}

Since each strcat invocation will append "a" to s, we should get a string of N letters 'a', assuming that N is less than 1000 (otherwise those letters won't fit in an array). But how many operations did this code execute?

Let's see: each strcat needs to find the end of the string s first, and then write one character and a trailing zero to the string.

When the string s is empty, its trailing zero is in the very beginning, so strcat will make only one comparison to find it. On the second iteration, s is "a", which is { 'a', 0 }, so it will need two loop iterations with comparison to find the end. On the third iteration, s is "aa" and three iterations will be needed.

As you remember from your algebra course, 1 + 2 + 3 + ... + N is (N+1)*N/2 (the sum of arithmetic sequence), so the total number of operations executed by our for loops is proportional to N²/2+N/2, which means the time complexity of the sequence of N strcat invocations is O(N²). This might be not what you expect! Quadratic algorithms become really slow if N is big (imagine the parabola), and it can cause real performance issues, so if you ever need to call strcat to append to the same string many times, you better think a little bit how to get rid of those extra operations: track the length of the resulting string and use strcpy to dest + length is one option, making your own version of strcat that returns a pointer to the end of the resulting string is another idea.

We'll see more quadratic algorithms later (when we talk about sorting)! For now we'll keep talking about strings.