7
\$\begingroup\$

Given a string A = "Hello world" and another string B = "wor", I have to print ("TRUE" or "FALSE") whether the characters in B are present in A. For example, if B = "ollw l" the result should be TRUE; if B = "worlds" the result should be FALSE; if B = "ww", result is FALSE. It has to be done in O(n) time complexity.

My solution is given below. Although this runs in O(n) time I would like some suggestions on how to improve.

int main(void)
{
        char *A = "Hello world";
        char *B = "ollw l";
        int table['z'] = {0};

        while (*A != '\0') {
                table[*A] += 1;
                A++;
        }

        while (*B != '\0') {
                table[*B] -= 1;
                if (table[*B] < 0) {
                        printf("%s\n", "FALSE");
                        return 0;
                }
                B++;
        }
        printf("%s\n", "TRUE");
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! Please don't forget to delete your question on Stack Overflow so you won't be accused of cross-posting. \$\endgroup\$ – 5gon12eder Jan 7 '17 at 14:15
  • \$\begingroup\$ @5gon12eder Yeah, i have flagged my question for deletion there. I can't delete on SO as someone has answered my question. \$\endgroup\$ – babon Jan 7 '17 at 14:19
  • \$\begingroup\$ Ok, well done, then. \$\endgroup\$ – 5gon12eder Jan 7 '17 at 14:21
  • 1
    \$\begingroup\$ @babon int table['z'] looks weird. what's your assumption about the actual size? \$\endgroup\$ – πάντα ῥεῖ Jan 7 '17 at 14:24
  • 1
    \$\begingroup\$ @babon "Are you saying it should be int table['z' + 1]?" No, I mean you should cover slots for any possible char value (or even better unsigned char value). \$\endgroup\$ – πάντα ῥεῖ Jan 7 '17 at 16:19
9
\$\begingroup\$

Your algorithm looks alright

The algorithmic idea seems correct and fit for meeting the stated requirements. There are also no unreasonable constant factors or excessive resource usage just to meet the required asymptotic complexity. Overall, I think you did the right thing.

Try to nail down the requirements

I'm not entirely sure what your function is supposed to do. Should it only take into account letters or also other characters like white-space and punctuation? Should it be case-sensitive or insensitive? Either choice is reasonable but one has to be made.

The following item is related to this.

Know your range

You're using an array from 0 (inclusive) to z (exclusive). As others have already pointed out in comments, this means an out of bounds access if the character z occurs in your input which is almost certainly a bug. Adding 1 to the array size might seem to fix the issue but I'd suggest to look more closer at the range of valid inputs.

First, you have to define your range of valid characters. This might be the whole range of the char data type. Which is implementation-defined so you should use the CHAR_MIN and CHAR_MAX macros defined in <limits.h>. (Your input actually can never contain the value 0 because you'd treat it as the sentinel value but wasting that one index seems reasonable.)

If your input range is smaller than that (for example, only ASCII characters or only alphanumeric characters), you should do two things.

  1. Verify that the input is in range and do some reasonable error handling if it is not. If you decide to give your function a narrow contract, invalid inputs mean undefined behavior and you can use the assert macro that is only active in debug builds and gain a little performance in release builds.

  2. Subtract the lowest permissible character from the character at hand to get the index in your array.

For the ASCII character set, the range is [0, 128) and [32, 126) for the printable sub-set. (It would probably be more readable to use ' ' (space) and '~' + 1 in code instead of these magic numbers.)

Be warned that the C standard doesn't require that the character set is ASCII and the ASCII math might be wrong for other encodings. Some encodings also have multi-byte characters and those will cause you never-ending nightmares if you wish to handle them correctly.

Beware of integral promotion

If your input can be the full range of the char data type, there is a nasty culprit here. The C standard doesn't specify whether char is signed or unsigned. If your code is used on an implementation where char is signed, the bytes 0x80 … 0xff will have negative numeric values.

If you compute your indices by subtracting CHAR_MIN, you'll be fine because it will make those values positive again. If you, however, expect values in the range [0, 256) you'll get bad surprises. The usual way to deal with this is to explicitly cast to unsigned char before using the value.

Consider saving some space – or maybe don't

You're currently using an int to count the frequency of a character. This is likely a reasonable choice but I'd like to challenge you to justify it.

If you want to be on the absolute safe side, a size_t will guarantee that you can even deal with the largest possible array, filled with the same character. If you go for size_t, be aware that it is an unsigned type so you cannot check for “less than zero” after the subtraction but have to check for “equal to zero” before subtracting.

If you want to preserve space (and thus get lower cache usage), you might want to reach for a smaller data type but you'll get undefined behavior if its range is exceeded.

Any decision can be justified but you should be aware of its implications. If your function makes assumptions about the maximum frequency of a character, its documentation should state this limitation.

Separate different concerns into different functions

You have put all code into main. This is obviously not a very modular design and hard to unit-test. I'd recommend that you break your logic into at least three functions.

  • One function that takes two character arrays and checks whether the former contains all characters from the latter. It doesn't print anything but returns a boolean value.
  • One function that converts a boolean value into a pointer to a statically allocated character array with a human-readable text. This can be as simple as return value ? "true" : "false";.
  • One function that obtains (or hard-codes) the input, calls the first function to get the result and then prints the human-readable representation obtained from the second function. (You can leave this logic in main if that's all your program does.)
\$\endgroup\$
  • 1
    \$\begingroup\$ You have some interesting points regarding the character set issues. +1 for that. \$\endgroup\$ – πάντα ῥεῖ Jan 7 '17 at 16:05
  • \$\begingroup\$ You won't see a performance increase by using a type smaller than the processor's native integer width (int). You might see a decrease in memory consumption if you're packing many such values into an array, but you'll pay a performance penalty to access them (and you might not even see a decrease in memory consumption if your optimizing compiler inserts packing to mitigate this performance penalty). \$\endgroup\$ – Cody Gray Jan 8 '17 at 6:45
  • \$\begingroup\$ @CodyGray The word “perform” was perhaps not a good choice here so I've reworded that sentence a little. The idea was that smaller data types use less memory and therefore less cache which might make the program faster. I wouldn't claim that it actually does or doesn't without benchmarking these things. I'm pretty sure, though, that a compiler is not allowed to add padding to an array, that is, sizeof(T[N]) == N * sizeof(T) is always true. \$\endgroup\$ – 5gon12eder Jan 9 '17 at 3:26
  • \$\begingroup\$ Hmm, that's true. Padding can't be added to an array, only a structure. But the larger point still stands, that this is "optimization" advice I see repeated a lot, without any real evidence behind it. And it is often followed as premature optimization without anyone actually taking the time to benchmark it because people are lazy and proper benchmarking is hard. \$\endgroup\$ – Cody Gray Jan 9 '17 at 12:16
4
\$\begingroup\$

As mentioned in 5gon12eder's answer the algorithm itself seems to be good and efficient. Setting up a table with the count of characters is a good idea to solve that problem efficiently.
Sorry, I missed to state that with my initial answer.

Though there are a number of points to be considered:

1. Don't make assumptions on the char set used

As I've menitoned in my comment

int table['z'] = {0};

is probably a bad idea:

  1. Don't assume an ASCII character set blindly, there are still others like EBCDIC in use and may screw up your assumptions
  2. If the input contains any other characters than expected you may hit undefined behavior because of the possibility that table is accessed out of range.

The better, and more generic way to adjust the possibly needed table array size is

int table[1 << CHAR_BIT] = {0};

The CHAR_BIT macro is accessible from limits.h.

2. Factor out your functionality to a separate function

This makes your code isolated, reusable and easier to test.

int check_match(char* A, char* B) {
    int table[1 << CHAR_BIT] = {0};
    while (*A != '\0') {
            table[*A] += 1;
            A++;
    }

    while (*B != '\0') {
        table[*B] -= 1;
        if (table[*B] < 0) {
            return 0;
            }
        B++;
    }
    return 1;
}

int main() {
    printf("%s\n",check_match("Hello world","ollw l")?"TRUE":"FALSE");
    printf("%s\n",check_match("Hello world","ww l")?"TRUE":"FALSE");
}

See Live Demo

3. Don't loose pointers initialized from literals

When you are incrementing your char* pointers A and B you are loosing the original literal reference.

That may be unwanted in some more complicated code that needs to refer to the literals later again.

Also make clear that the literals shouldn't be overwritten using the const keyword, since this would lead to undefined behavior:

const char *A = "Hello world";
const char *B = "ollw l";

4. Consider to use the current c standard (C99)

Compiling your (or my proposed) code with the C99 strict options throws some warnings/errors like

prog.c: In function 'check_match':
prog.c:7:22: error: array subscript has type 'char' [-Werror=char-subscripts]
             table[*A] += 1;

You can fix this using a cast to size_t which should be the actual type used for array indexing.


You can check my finally fixed code with all the mentioned points from above here.

\$\endgroup\$
  • \$\begingroup\$ I you use 1 << CHAR_BIT, you can still be in trouble on implementations where char is signed, regardless of the encoding. (Which, at least to me, is much more relevant than EBCDIC platforms.) \$\endgroup\$ – 5gon12eder Jan 7 '17 at 15:59
  • \$\begingroup\$ @5gon12eder Well, I think that's probably covered in my point 4., isn't it? \$\endgroup\$ – πάντα ῥεῖ Jan 7 '17 at 16:08
  • \$\begingroup\$ Yes, that's true. Casting to size_t would solve it. I didn't realize that the warning was related to that because it warns about char, not the signedness. It would be interesting to know whether GCC also emits the warning on platforms where char is unsigned (if GCC supports any of them at all). \$\endgroup\$ – 5gon12eder Jan 9 '17 at 3:14
2
\$\begingroup\$

table['z'] too small.

Code makes a table the size of 'z', which is 1 too small should *A == 'z'. This leads to undefined behavior (UB) and code should be amended to handle all letters.

    int table['z'] = {0};
    while (*A != '\0') {
            table[*A] += 1;  // table['z'] indexes pass the end of the array.

The above code also has trouble when:
1) *A is some character with values even greater than 'z'
2) When char is signed and *A has a negative value.

A simple solution is to create an array that is sized to all char and to access that array offset by the minimum value.

    #include <limits.h>
    int table[CHAR_MAX - CHAR_MIN + 1] = {0};
    while (*A != '\0') {
            table[*A - CHAR_MIN] += 1;

On rare machines, CHAR_MAX - CHAR_MIN is a large value exceeding memory and another approach is needed.


Detail on "this runs in O(n)".

Code first initializes with int table['z'] = {0};. This takes a fixed amount of time. From an efficiency stand point, the initialization can dominate run time when the string length n is small. If the target use of this algorithm was applied to many small strings, a different approach should be considered.

Code could vector on the initial portion of the string. If A was at least of length n (maybe 4 to 8), then proceed with your current approach. With small a short string, simple compare each character of B against each character of A. If this extra code is worth it or not depends on various things.

The point being that a simple pre-analysis of the arguments A and B could be used to steer which algorithm is used. The major downs-side is more code to develop, rate and maintain.

\$\endgroup\$
  • \$\begingroup\$ "On rare machines, CHAR_MAX - CHAR_MIN is a large value...." I am curious-- do you mean machines with 32 bit chars? Small stack limits? If yes, have you encountered such a machine in the real world? \$\endgroup\$ – David Bowling Jan 11 '17 at 2:28
  • 1
    \$\begingroup\$ @DavidBowling I have encountered 9-bit BITD, and 8-bit signed/unsigned char and have heard tell of 64-bit char/short/int/long/long long. Perhaps it was some graphics processor. The C spec is certainly not limited to my experiences, so I comment based on the spec. \$\endgroup\$ – chux - Reinstate Monica Jan 11 '17 at 3:10
  • \$\begingroup\$ 64-bit chars seems remarkable! I am all for coding with the Standard firmly in mind, and certainly did not mean to criticize; this seemed like a subtle issue and a good catch. I was merely curious :) \$\endgroup\$ – David Bowling Jan 11 '17 at 4:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.