Replace a string in C without string.h library

Question

I want to make a function which will replace two strings without using <string.h> library. In order to achieve that, I used 6 manually written functions which are together achieving this task. I have a small problem with this code, this doesn't check if string which will be replaced is word which is completely equal to replacing string.

For example:

char s[] = "Why is ostring in C so hard",
     change_what[] = "string",
     into_what[] = "pointers";

OUTPUT should be:

"Why is ostring in C so hard"

Because "ostring" is not completely equal to "string".

My output is:

"Why are opointers in C so hard"

Code:

#include <stdio.h>

int compare(char *x, char *y)
{
    while (*x != '\0' || *y != '\0')
    {
        if (*x == *y)
        {
            x++;
            y++;
        }
        // if they are not equal
        else if ((*x == '\0' && *y != '\0') || (*x != '\0' && *y == '\0') ||
                 *x != *y)
        {
            return 0;
        }
    }
    return 1;
}

int lenght(char *a)
{
    char *b;
    for (b = a; *a; a++)
        ;
    return a - b;
}

char *substring(char *main_string, char *substring) {
    while (*main_string != '\0') {
        char *p = main_string;
        char *q = substring;
        while (*p++ == *q++) {
            if (*p == ' ' || *p == '\0')
               if (*q == '\0') {
                   return main_string;
            }
        }
        main_string++;
    }
    return NULL;
}

void replace_string_add(char *s, char *change_what, char *into_what,
                        int shift)
{
    char *i_pointer = into_what;
    char *c_pointer = change_what;
    char *position = substring(s, change_what);
    while (position != NULL)
    {
        char *end = position;
        while (*end != '\0')
        {
            end++;
        }
        while (end > position)
        {
            *(end + shift) = *end;
            end--;
        }
        while (*into_what != '\0')
        {
            *position++ = *into_what++;
        }
        position = substring(s, change_what);
        into_what = i_pointer;
        change_what = c_pointer;
    }
}

void replace_string_remove(char *s, char *change_what, char *into_what,
                           int shift)
{
    char *i_pointer = into_what;
    char *c_pointer = change_what;
    char *position = substring(s, change_what);
    while (position != NULL)
    {
        char *temp = position;
        while (*(temp + shift) != '\0')
        {
            *temp = *(temp + shift);
            temp++;
        }
        *temp = '\0';
        while (*into_what != '\0')
        {
            *position++ = *into_what++;
        }
        position = substring(s, change_what);
        into_what = i_pointer;
        change_what = c_pointer;
    }
}

void replace_string(char *s, char *change_what, char *into_what)
{
    int shift = lenght(into_what) - lenght(change_what);
    if (compare(change_what, into_what) == 0)
    {
        if (shift >= 0)
        {
            replace_string_add(s, change_what, into_what, shift);
        }
        else
        {
            replace_string_remove(s, change_what, into_what, -shift);
        }
    }
}

int main()
{
    char s[] = "Why is ostring in C so hard",
         change_what[] = "string",
         into_what[] = "pointers";
    replace_string(s, change_what, into_what);
    printf("\"%s\"", s);
    return 0;
}

If string is "Why is strings in C so hard" program would work correct because it checks if last characters are ' ' or '\0'.

"Why is ostring in C so hard" wouldn't work, because it doesn't check first character. Could you help me modify this code to check also first character?

Note: auxiliary strings and dynamic allocation are not allowed

string.h is not a library. It is a header which declares functions that are in the standard library. — William Pursell
– William Pursell, Commented Feb 15, 2022 at 12:33
"strings" is not completely equal to "string", but "string" is completely equal to "string" and that is the substring that was found. You need to define the delimiting conditions for the beginning and end of potentially matching substrings. — Ian Abbott
– Ian Abbott, Commented Feb 15, 2022 at 12:33
So it would appear that you're not actually reading a word, but substituting matches. A word is defined as a series of characters that are delimited by either a space (' ') or a null value. — ChrisBD
– ChrisBD, Commented Feb 15, 2022 at 12:34
If dynamic allocation is not allowed, among other changes you'll want to do something like char s[1024]="Why are strings in C so hard" to avoid overflowing the buffer. And add bounds checking. — William Pursell
– William Pursell, Commented Feb 15, 2022 at 12:36
"Note: auxiliary strings and dynamic allocation are not allowed" - well that's going to come back to bite you hard then, because s in main has space for exactly 29 characters including the terminator, your 'replacement' will result in a string 30 characters long including the terminator. E.g. you're trying to stuff 30 pounds of nuts in a 29 pound bag. You need to change s to allow for the extra required space. — WhozCraig
– WhozCraig, Commented Feb 15, 2022 at 12:38

chqrlie · Accepted Answer · 2022-02-15 19:14:59Z

Your program has multiple issues:

there is a lot of redundant code in the compare function. You can simplify it as:

int compare(const char *x, const char *y) {
    while (*x != '\0' || *y != '\0') {
        if (*x == *y) {
            x++;
            y++;
        } else {
            return 0;
        }
    }
    return 1;
}

or even further:

int compare(const char *x, const char *y) {
    while (*x++ == *y++) {
        if (x[-1] == '\0')
            return 1;
    }
    return 0;
}

the lenght function should be named length

substring checks for a space after the end of the substring, but does not check for a space before the start. It also has undefined behavior if the substring matches the end of the main_string because characters beyond the null terminator will be accessed. Here is a modified version:

char *substring(char *main_string, const char *substring) {
    char *p = main_string;
    char last = ' ';
    while (*p != '\0') {
        if (last == ' ') {
            size_t i = 0;
            while (substring[i] != '\0' && p[i] == substring[i]) {
                i++;
            }
            if (substring[i] == '\0' && (p[i] == ' ' || p[i] == '\0')) {
                return p;
            }
        }
        last = *p++;
    }
    return NULL;
}

in replace_string_add and replace_string_remove, c_pointer is useless and it would be less confusing to use i_pointer to copy the replacement than modify into_what and restore it.

Note also that the main_string argument must have enough space for the replacements, which would not be the case in the example if the change_what string was "ostring".

Here is a modified version:

#include <stdio.h>

int compare(const char *x, const char *y) {
    while (*x++ == *y++) {
        if (x[-1] == '\0')
            return 1;
    }
    return 0;
}

int length(const char *a) {
    const char *b;
    for (b = a; *a; a++)
        continue;
    return a - b;
}

char *substring(char *main_string, const char *substring, int len) {
    char *p = main_string;
    char last = ' ';
    while (*p != '\0') {
        if (last == ' ') {
            int i = 0;
            while (i < len && p[i] == substring[i]) {
                i++;
            }
            if (i == len && (p[i] == ' ' || p[i] == '\0')) {
                return p;
            }
        }
        last = *p++;
    }
    return NULL;
}

char *replace_string(char *s, const char *change_what, const char *into_what) {
    int what_len = length(change_what);
    int into_len = length(into_what);
    int shift = into_len - what_len;
    int i;
    char *pos = s;

    if (shift == 0 && compare(change_what, into_what))
        return s;

    while (*pos && (pos = substring(pos, change_what, what_len)) != NULL) {
        if (shift > 0) {
            for (i = length(pos); i >= what_len; i--) {
                pos[i + shift] = pos[i];
            }
        } else
        if (shift < 0) {
            for (i = into_len; ((pos[i] = pos[i - shift]) != '\0'; i++) {
                continue;
            }
        }
        for (i = 0; i < into_len; i++) {
            *pos++ = into_what[i];
        }
        if (*pos == ' ') {
            pos++;
        }
    }
    return s;
}

int main() {
    char s[100] = "Why is ostring in C so hard";
    printf("\"%s\"\n", replace_string(s, "string", "pointer"));
    printf("\"%s\"\n", replace_string(s, "ostring", "pointers"));
    printf("\"%s\"\n", replace_string(s, "is", "are"));
    printf("\"%s\"\n", replace_string(s, "hard", "cool"));
    printf("\"%s\"\n", replace_string(s, "pointers", "strings"));
    printf("\"%s\"\n", replace_string(s, "in C", ""));
    printf("\"%s\"\n", replace_string(s, "", "in C++ not"));
    printf("\"%s\"\n", replace_string(s, "", ""));
    return 0;
}

Output:

"Why is ostring in C so hard"
"Why is pointers in C so hard"
"Why are pointers in C so hard"
"Why are pointers in C so cool"
"Why are strings in C so cool"
"Why are strings  so cool"
"Why are strings in C++ not so cool"
"Why are strings in C++ not so cool"

Learn by example! Try and optimize this case: replacing aa with a in a string with many occurrences of aa will make many intermediary copies... make it run in O(n) time by using 2 pointers: one for reading and one for writing.

chqrlie · Accepted Answer · 2022-02-15 15:13:18Z

0

ok clear, I think it's easier to use a string tokenizer for this. The following code first copies s into s2 and then puts a '\0' at every space and keeps track of how many words there are. the first for loop. Then clear out s and loop through s2 stopping at every '\0' sentinel and check if every word equals your replace word. If it matches copy back the replace word otherwise the original word.

#include <stdio.h>

static void cat(char *d, char *s)
{
    char *p;
    for (p = d; *p; p++);
    
    for (char *p2 = s; *p2;)
      *p++ = *p2++;
    *p = 0;
}

static int cmp(char *s1, char *s2)
{
    char *p1 = s1, *p2 = s2;
    
    while (*p1 && *p2 && *p1 == *p2)
    {
        p1++;
        p2++;
    }

    if (*p1 == 0 && *p2 == 0) return 0;
    
    return -1;
}

int main()
{
    char s[100]="Why are strings in C so hard",change_what[]="strings", into_what[]="pointers";
    
    char s2[100];
    
    for (char *p = s, *p2 = s2; *p2=*p; p++, p2++);
    
    int countwords = 0;
    
    for (char *p = s2; *p; p++)
       if (*p == ' ') { *p = '\0'; countwords++; }

    int current = 0;
    
    char *s3 = s2;
    *s = '\0';
    
    while (current <= countwords)
    {
        char *p = s3;
        for (; *p; p++);
        
        if (cmp(s3, change_what) == 0)
            cat(s, into_what);
        else
            cat(s, s3);
            
        cat(s, " ");
            
        s3 = p + 1;

        current++;
    }
    
    printf("%s\n", s);
    
    return 0;
}

edited Feb 15, 2022 at 15:13

chqrlie

152k12 gold badges145 silver badges231 bronze badges

answered Feb 15, 2022 at 12:48

Serve Laurijssen

9,9606 gold badges55 silver badges109 bronze badges

4 Comments

Lundin Over a year ago

"Use the string.h library" is not a great answer to the question "Replace a string in C without string.h library". Obviously it can be made more elegant by using all these functions, but the task here rather seems to be understanding of how the string.h functions are implemented underneath the hood. So this doesn't answer the question.

Serve Laurijssen Over a year ago

the point was the tokenizing, not the compare and concat functions but anyway changed it

user17936437 Over a year ago

@ServeLaurijssen You used auxiliary string which is not allowed

user17936437 Over a year ago

your code adds one extra space on the end, try it with printf("\"%s\"", s);

Collectives™ on Stack Overflow

Replace a string in C without string.h library

2 Answers 2

2 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related