8
\$\begingroup\$

Works fine. Not looking for any specific input.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000


void delete_str(char *s1, char *s2){
    for(int i = 0; *(s1+i) != '\0'; ++i){
        for(int j = 0; *(s2+j) != '\0'; ++j){
            if(*(s1+i) == *(s2+j)){
                for(int n = i; *(s1+n) != '\0'; ++n){
                    *(s1+n) = *(s1+n+1);
                }
                --i;
                break;
            }
        }
    }
}

int main(void){
    char s1[MAX_SIZE];
    char s2[MAX_SIZE];

    puts("Enter s1");
    if(fgets(s1, sizeof(s1), stdin) == NULL){
        puts("Error reading s1");
        exit(EXIT_FAILURE);
    }

    puts("Enter s2");
    if(fgets(s2, sizeof(s2), stdin) == NULL){
        puts("Error reading s2");
        exit(EXIT_FAILURE);
    }

    delete_str(s1, s2);

    printf("%s", s1);

    return 0;
}
\$\endgroup\$
12
\$\begingroup\$

This compiles cleanly with no warnings, so a positive there.

You may find it easier to use command-line input rather than fgets() for the following reasons:

  1. You don't need to decide on a maximum input size in advance
  2. You can have any character (including newline) in your strings

On the flip side, you do have to be able to write the strings as single arguments; you'll have to be comfortable with your shell's quoting and character escapes.

I would re-write the main() like this:

int main(int argc, char **argv)
{
    if (argc != 3) {
        fprintf(stderr, "Usage: %s string chars-to-delete\n", argv[0]);
        return EXIT_FAILURE;
    }

    delete_str(argv[1], argv[2]);
    puts(argv[1]);
}

Two other things I changed:

  1. Error message should go to stderr. Your use of EXIT_FAILURE is perfectly right, and I've kept that (though I find plain return simpler than exit(), and in C++ it may be better to ensure destructors get called).
  2. We don't necessarily have a terminating newline in the string (as we did with fgets()), so we can use puts() instead of printf("%s", s1) - but well done for avoiding the trap of printf(s1) which would be wrong and dangerous.

Turning now to delete_str itself, you might want to change s2 from char* to const char*, as we're not modifying the second argument. That helps clarify which argument is which, too.

The first thing I note is that the array indexing *(s1+i) is usually written s1[i], and doing so will make your intent clearer to other C programmers:

void delete_str(char *s1, const char *s2)
{
    for (int i = 0;  s1[i] != '\0';  ++i) {
        for (int j = 0;  s2[j] != '\0';  ++j) {
            if (s1[i] == s2[j]) {
                for (int n = i;  s1[n] != '\0';  ++n) {
                    s1[n] = s1[n+1];
                }
                --i;
                break;
            }
        }
    }
}

One thing that will slow your program down is that each time you delete any of the matched characters, you copy the whole of the rest of s1 to close up the gap. Instead of doing that, you can keep track of two positions: the next character to be read and the next character to be written. These will start off at the beginning of s1, but each time a character is skipped, the read position will advance, and the write will not. I'll call these src and dest, and I'll make them pointers (rather than indexes into s1). We get to replace the inner (n) loop:

void delete_str(char *s1, const char *s2)
{
    char *dest = s1;
    for (const char *src = s1;  *src != '\0';  ++src) {
        *dest++ = *src;
        for (int j = 0;  s2[j] != '\0';  ++j) {
            if (*src == s2[j]) {
                --dest;
                break;
            }
        }
    }
    *dest = '\0';
}

We can also lean on the standard library. There's strchr(const char *s, int c), which will return a pointer into s if it contains c, or a null pointer if not. So we can test if *src is in s2 with a simple call (replacing the j loop):

#include <string.h>

void delete_str(char *s1, const char *s2)
{
    char *dest = s1;
    for (const char *src = s1;  *src != '\0';  ++src) {
        if (strchr(s2, *src) == NULL)
            *dest++ = *src;
    }
    *dest = '\0';
}

We can do better: the standard library also contains strspn and strcspn which tell us how many characters to skip and how many to copy. We can use that to copy whole chunks of input, like this:

void delete_str(char *s1, const char *s2)
{
    char *dest = s1;
    for (const char *src = s1;  *src;  src += strspn(src, s2)) {
        int n = strcspn(src, s2);
        memmove(dest, src, n);
        dest += n;
        src += n;
    }
    *dest = '\0';
}

I note also that we never use s1 again, so we could just use that in place of dest.


My version

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

void delete_str(char *s1, const char *s2)
{
    for (const char *src = s1;  *src;  src += strspn(src, s2)) {
        int n = strcspn(src, s2);
        memmove(s1, src, n);
        s1 += n;
        src += n;
    }
    *s1 = '\0';
}

int main(int argc, char **argv)
{
    if (argc != 3) {
        fprintf(stderr, "Usage: %s string chars-to-delete\n", argv[0]);
        return EXIT_FAILURE;
    }

    delete_str(argv[1], argv[2]);
    puts(argv[1]);
}

It is possible (and perhaps faster) to use a table-based approach. Create an array of booleans (i.e. any integer type, but probably uint_fast8_t from <stdint.h> for speed, or char if size is most important), and toggle each position that's mentioned in s2 (remember to convert to unsigned, as plain char may or may not be a signed type). You might want to benchmark to see which is faster, and for which inputs:

#include <limits.h>
#include <stdint.h>
#include <string.h>

void delete_str(char *s1, const char *s2)
{
    typedef uint_fast8_t flag_type;
    flag_type allowed[1 << CHAR_BIT];
    memset(allowed, 1, sizeof allowed);
    while (*s2)
        allowed[(unsigned char)*s2++] = 0;

    for (const char *src = s1;  *src;  ++src) {
        if (allowed[(unsigned char)*src])
            *s1++ = *src;
    }
    *s1 = '\0';
}
\$\endgroup\$
  • \$\begingroup\$ What if I have the string: "Hello my name is Toby", and I want to delete "ea o". That no longer works. Or maybe I'm using the command line arguments incorrectly. \$\endgroup\$ – user127566 Mar 20 '17 at 11:46
  • 1
    \$\begingroup\$ Works for me, in Bash: ./158275 "Hello my name is Toby" "ea o" prints HllmynmisTby, which I think is correct. Did you get or expect something different? \$\endgroup\$ – Toby Speight Mar 20 '17 at 11:48
  • \$\begingroup\$ Okay. I was using them incorrectly. \$\endgroup\$ – user127566 Mar 20 '17 at 11:51
  • \$\begingroup\$ @Jack, this is a read/write pointer approach. Did you mean that a table will be faster than strcspn? That's probably right, if you can amortize the setup cost of the table. I think the crossover is pretty near, but haven't done any profiling. \$\endgroup\$ – Toby Speight Mar 20 '17 at 17:32
  • \$\begingroup\$ My bad. I misread your code. Sorry. \$\endgroup\$ – Jack Aidley Mar 20 '17 at 17:51
4
\$\begingroup\$

Your comparison occurs inside of two nested loops of size of the strings (say, n and m). Another loop is used for the deletions in the first string. All of the loops are dependent on the size of the concerned strings, so your algorithmic complexity is O(n^2*m).

Assuming typical definitions of "char" (commonly 8bit) you can do a whole lot better. First create a bitmap or an array of bool that will tell for each possible character value whether or not it is contained in your second string.

You initialize to zero (fixed cost), then loop through your second string, use its characters as indexes into the bitmap and set the corresponding bits/booleans. This is O(m) with m the size of the second string.

Then you loop through the first string with a write and a read pointer both initialized to its start. For each character you read via the read pointer, you check whether or not the bitmap signals that it is part of the second string. If it isn't, you write the read character at the write pointer and advance both read and write pointers. If it is, you just advance the read pointer. Do this until the read pointer reaches the end of the original string 1, don't forget to copy the final zero.

Again, this loop is only nesting one level deep, so since the bitmap accesses cost constant time, the whole algorithm is O(n+m) with a reasonably cheap one-time setup. Which sure beats O(n^2*m) unless either n or m is zero (but even with m zero, your algorithm still has the outer loop running).

\$\endgroup\$
  • \$\begingroup\$ For a short strings and few characters to remove, your "cheap one-time setup" may well take more time than it saves. \$\endgroup\$ – Jack Aidley Mar 20 '17 at 15:26
  • \$\begingroup\$ @JackAidley, I highly doubt that. The cheap one-time setup incurs exactly one loop over the forbidden string. The slow solution performs one loop over the forbidden string for each character in the input string. Thus, one should expect it to be faster only when the input string contains zero characters (which you can obviously special-case if you really care). Furthermore, there are no "hidden costs": the 256 bits (or bytes, which may be easier) of memory will be allocated and zero-initialized statically, and cache performance will be even better than in the slow solution. \$\endgroup\$ – wchargin Mar 20 '17 at 16:41
  • \$\begingroup\$ Static initialization may happen on a single use - which to be fair is the case in the exact scenario presented - but in general will require zero initialization of the whole array which is quick but not free. \$\endgroup\$ – Jack Aidley Mar 20 '17 at 17:51
1
\$\begingroup\$

Your naming is poor

Good naming is one of the most important skills in programming. In this case, delete_str is a very bad name for this function, and s1 and s2 are bad names for the arguments. Nothing about any of these names communicates their function. delete_str is particularly bad because it implies that the function will delete a string, and it doesn't, whereas s1 and s2 are merely completely devoid of any descriptive content.

There are many possible names, but I would suggest something like void remove_matching(char *target, const char *to_remove) although you could go for more descriptive and verbose naming such as void remove_matching_characters(char* target_string, const char* characters_to_remove). There is always a trade-off to be made between being descriptive and being long-winded, and you will need to judge that for yourself. In every case, however, the names should be descriptive.

\$\endgroup\$
  • 2
    \$\begingroup\$ Good point. Surely, to follow the same naming conventions as the standard libraries, the function should be named strrmmch! :-) \$\endgroup\$ – wchargin Mar 20 '17 at 16:42
  • 2
    \$\begingroup\$ @wchargin - the original C libraries had to work with linkers that only checked the first six characters for a match, so you'd probably want something a bit shorter... \$\endgroup\$ – Toby Speight Mar 20 '17 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy