# Determine if one string occurs at the end of another

### 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;
}

-

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).

-
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 '14 at 16:19
@Josay I agree, I should be more consistent. The edit has been made (and the upvote already reciprocated ;)). – syb0rg Jun 19 '14 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 '14 at 0:18
@PierreMenard Correct, I'm not sure what I was thinking. An edit has been made. – syb0rg Jun 20 '14 at 1:47
@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 '14 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.....

-
The text does end with and man -> The text does end with an man – Marc-Andre Jun 19 '14 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);
}

-
I would store the string length values so you don't have to recalculate them. Otherwise, you have earned my +1! – syb0rg Jun 19 '14 at 16:33
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 '14 at 23:02
Note: The difference of strlen(s)-strlen(t) may not fit in an int. – chux Jun 21 '14 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 '14 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 '14 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;
}

-