Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Exercise 5-4

Write the function strend(s,t), which returns one if the string t occurs at the end of the string s, and zero otherwise.

#include <stdio.h>

int str_end(const char *, const char*);

int main(void)
{
    char *s1 = "Man is a rope stretched over an abyss.";
    char *s2 = "an abyss.";

    printf("%s\n", str_end(s1, s2) ? "Yes" : "No");
    return 0;
}

int str_end(const char *s, const char *t)
{
    const char *init = t;       /* Hold the initial position of *t */

    while (*s) {
        while (*s == *t) { 
            if (!(*s)) {
                return 1;
            }
            s++;
            t++;
        }
        s++;
        t = init;
    }
    return 0;
}
share|improve this question

4 Answers 4

up vote 15 down vote accepted

A few notes:

  • Analyzing your code, I see a simple bug that isn't accounted for. Consider the following case:

    char *s1 = "Man is a rope stretched over an abyss.";
    char *s2 = "an abyss..c9f0c50bc2e417b078e3b0bf82d5386d418cfba4";
    

    Your method still returns 1 even though it clearly shouldn't, because you only checked for \0 in *s and not in *t. You need to check if the NULL terminators are in matching positions. Also, s2 is clearly a larger string than s1, we never compared the lengths to see if s2 could even fit into s1.

  • You are somewhat approaching this inefficiently. You are comparing all of the characters in the string. You don't need to do this, we can just compare at the index strlen(s) - strlen(t).

  • You could shorten your while loop a bit.

        while (*s == *t) { 
            if (!(*s)) {
                return 1;
            }
            s++;
            t++;
        }
    

    Increment *s and *t inside of your while test conditional.

  • You could also forgo the while loop completely and use the standard function strncmp(). However, I would use memcmp() since it is faster.

  • You wouldn't need the function prototype if you define your strend() function before you define main().

  • What if you pass an invalid string to your function? Right now it can't handle it and will throw a "Segmentation fault". That's not any fun, so let's implement a simple test to check for that.

    if (!s || !t) return 0;
    

    Based on the discussion between @RolandIllig and myself, I have decided to not implement this check. Why? Because this is a runtime check that comes with a certain overhead time to process. That time may not be much, but on certain systems (such as embedded ones) that processing power would be better used somewhere else. Therefore, I decided to follow the philosophy behind the design of the C standard library: that the programmer is ultimately in the best position to know whether a runtime check really needs to be performed.

  • I'm not sure how you want to handle empty strings. I'm not going to mess with that too much since there was nothing stating so in the exercise.

  • You should document all of your code. Even for a simple function such as this.


Final Product

#include <string.h>  // strlen(), memcmp()

/**
 * @fn int strend(const char *s, const char *t)
 * @brief Searches the end of string s for string t
 * @param s the string to be searched
 * @param t the substring to locate at the end of string s
 * @return one if the string t occurs at the end of the string s, and zero otherwise
 */
int strend(const char *s, const char *t)
{
    size_t ls = strlen(s); // find length of s
    size_t lt = strlen(t); // find length of t
    if (ls >= lt)  // check if t can fit in s
    {
        // point s to where t should start and compare the strings from there
        return (0 == memcmp(t, s + (ls - lt), lt));
    }
    return 0; // t was longer than s
}

Tests and Benchmarking

Here are a few trial runs I did of the method, and their output. All seems well by the tests.

  • strend("Man is a rope stretched over an abyss.", "an abyss..c9f0c"); returns 0.

  • strend("Man is a rope stretched over an abyss.", "an abyss"); returns 0.

  • strend("Man is a rope stretched over an abyss.", "an abyss."); returns 1.

  • strend("Man is an man man.", "an man."); returns 1.

  • strend("an abyssan abyssan abyssan abyss.", "an abyss."); returns 1.

  • strend(NULL, NULL); returns 0.

Using a benchmarking program I wrote to profile the code, I tested your function as well as the others supplied against mine. Here are the results, averaged out over 100000000 test iterations:

Search string: simple
End string: le
syb0rg's function average runtime: 1.47728e-08 seconds
ao2130's function average runtime: 1.87163e-08 seconds
Edward's function average runtime: 2.29287e-08 seconds
Josay's function average runtime: 2.58304e-08 seconds

Search string: this is a test
End string: test
syb0rg's function average runtime: 1.81173e-08 seconds
ao2130's function average runtime: 4.7522e-08 seconds
Edward's function average runtime: 2.31506e-08 seconds
Josay's function average runtime: 4.62652e-08 seconds

Search string: this is a longer string and may cause certain functions to take a bit longer to process
End string: a bit longer to process
syb0rg's function average runtime: 3.17312e-08 seconds
ao2130's function average runtime: 2.44403e-07 seconds
Edward's function average runtime: 3.33028e-08 seconds
Josay's function average runtime: 3.25736e-07 seconds

As you can see, my function runs a tiny bit faster than yours and the other functions supplied here (watch the scientific notation).

share|improve this answer
    
This looks like a good solution to me (on my side I decided not to use strlen to be able to stop quickly is a string is order of magnitudes longer than the other) : you deserve my upvote. However, if you are to use the standard function, shouldn't you use strcmp to compare directly t and s+ls-lt ? –  Josay Jun 19 at 16:19
    
@Josay I agree, I should be more consistent. The edit has been made (and the upvote already reciprocated ;)). –  syb0rg Jun 19 at 16:31
    
re: silence compiler warning "Control may reach end of non-void function" You reach this when the strings have incompatible length, so it's not the spurious warning that the comment implies. –  Pierre Menard Jun 20 at 0:18
    
@PierreMenard Correct, I'm not sure what I was thinking. An edit has been made. –  syb0rg Jun 20 at 1:47
1  
@RolandIllig Those checks should be there. Without that check, if we submit a NULL char* we get a Segmentation fault. We want to check for corner cases like that so that people using the function can rely on it in all circumstances. –  syb0rg Jun 22 at 20:01

Unfortunately your code has a bug. If there is a mis-match on the end-string, you roll-back the pointer for the end-string to the init value. You should also roll-back the pointer in the s string so that you can look for cases where the actual result starts part-way through the failed match.

This is easier to describe with an example. Consider the nonsense input values:

Man is an man man

with the search phrase:

an man

The text does end with an man, but your code will say it does not. Here is an ideone showing this problem.

You need to back-track your text pointer as well as the search pointer.

And, in other news, the variable names s and t are not very descriptive, and makes it hard to simply read your code. Consider names like text and search, or something that actually describes what the variables are.....

share|improve this answer
    
The text does end with and man -> The text does end with an man –  Marc-Andre Jun 19 at 16:52

A simpler way to do this would be to start from the end instead of the beginning.

int str_end(const char *s, const char *t)
{
    if (strlen(s) < strlen(t)) return 0;
    return 0 == strcmp(&s[strlen(s)-strlen(t)], t);
}

To avoid calling strlen more than needed, this code is slightly faster:

int str_end(const char *s, const char *t)
{
    int diff = strlen(s)-strlen(t);
    return diff > 0 && 0 == strcmp(&s[diff], t);
}
share|improve this answer
1  
I would store the string length values so you don't have to recalculate them. Otherwise, you have earned my +1! –  syb0rg Jun 19 at 16:33
2  
I don't think it matters how you store the lengths; you still have to strlen() both strings, which is dramatically more expensive than storing an integer in memory. –  Wug Jun 19 at 23:02
2  
Note: The difference of strlen(s)-strlen(t) may not fit in an int. –  chux Jun 21 at 6:28
    
I read that you should cast out of size_t when using values from strlen() etc, as it can have side effects. Is this what you are talking about chux? –  ao2130 Jun 21 at 12:33
    
@ao2130: The issue is signed versus unsigned. size_t is an unsigned quantity but int is obviously signed. Also discussed in this question –  Edward Jun 21 at 13:26

I was about to say that I had found a bug with the following test cases while trying to understand how your logic works :

char *s1 = "an abyssan abyssan abyssan abyss.";
char *s2 = "an abyss.";

char *s1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.";
char *s2 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaa.";

I reckon you should start by writing test cases and check that your code produces the results you are expecting.

For instance, here is what I have written. I won't say it's bug free because I haven't spent much time on it but at least I have a bit of confidence because it seems to go through the different tests I have written :

#include <stdio.h>
#include <assert.h>

int str_end(const char *s, const char *t)
{
    // Going forward on both strings til we reach an end
    int l;
    for (l=0; *s && *t; s++, t++, l++);

    // If t is not over ... 
    if (*t)
    {
        // ... then s should be
        assert(!*s);
        // so s is shorter and there is no point in going further
        return 0;
    }

    assert(!*t);

    // Going forward on s
    for ( ; *s; s++);

    // Going backward on both -- this could also be done with a normal string comparison function by going back l steps and comparing remaining strings
    for ( ; l>=0; l--, s--, t--)
        if (*s != *t)
            return 0;
    return 1;
}

int main(void)
{
    assert( str_end("Man is a rope stretched over an abyss.", "an abyss."));
    assert(!str_end("Man is a rope stretched over an abyss.", "un abyss."));
    assert( str_end("Man is a rope stretched over an abyss.", ""));
    assert( str_end("", ""));
    assert( str_end(".", "."));
    assert( str_end(".", ""));
    assert(!str_end("", "."));
    assert( str_end("qqqqqqqqqqqqqqqqqqqqqqqqqq", "qq"));
    return 0;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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