Asp Forum - K&R2, exercise 5-4, strend(s,t

arnuld

6/23/2011 10:56:00 AM

K&r2, exercise 5-4, page 107

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

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

int strend(const char* s1, const char* s2);

int main(void)
{
const char* arr1 = "comp.lang.c";
const char* arr2 = "comp.lang.";

printf("strend(%s, %s) = %d\n", arr1, arr2, strend(arr1, arr2));

return 0;
}

/* return 1 if str2 occurs at the end of str1, zero otherwise */
int strend(const char* str1, const char* str2)
{
int ret;

/* If one of arguments is NULL, there is no pint in going next */
if(NULL == str1 || NULL == str2)
{
ret = 0;
}
else if(strlen(str1) < strlen(str2))
{
ret = 0;
}
else if ('\0' == *str1 && '\0' == *str2)
{
ret = 1;
}
else
{
size_t len1 = strlen(str1);
size_t len2 = strlen(str2);
const char* tmp1 = str1 + len1 - 1;
const char* tmp2 = str2 + len2 - 1;
size_t count = 0;
for(; *tmp1 == *tmp2 && count < len2; --tmp1, --tmp2, ++count)
;

if(count == len2 && *++tmp1 == *++tmp2) ret = 1;
else ret = 0;
}

return ret;
}

==================== OUTPUT =========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra strend.c
[arnuld@dune C]$ ./a.out
strend(comp.lang.c, comp.lang.) = 0
[arnuld@dune C]$

--
www.lispmachine.wordpress.com
find my email-ID @above blog

15 Answers

Ian Collins

6/23/2011 11:04:00 AM

On 06/23/11 10:56 PM, arnuld wrote:
> K&r2, exercise 5-4, page 107
>
> Write the functions strend(s,t), which returns 1 if the string t occurs
> at the end of the string s, and zero otherwise.
>
>
> #include<stdio.h>
> #include<string.h>
>
> int strend(const char* s1, const char* s2);
>
>
> int main(void)
> {
> const char* arr1 = "comp.lang.c";
> const char* arr2 = "comp.lang.";
>
> printf("strend(%s, %s) = %d\n", arr1, arr2, strend(arr1, arr2));

You should add test cases for the conditions you are testing as well as
some matches.

> return 0;
> }
>
>
> /* return 1 if str2 occurs at the end of str1, zero otherwise */
> int strend(const char* str1, const char* str2)
> {
> int ret;
>
> /* If one of arguments is NULL, there is no pint in going next */
> if(NULL == str1 || NULL == str2)
> {
> ret = 0;
> }
> else if(strlen(str1)< strlen(str2))

I would do this test last, after you assign the strlen results to len1
and len2 to avoid calling strlen twice for each string.

> {
> ret = 0;
> }
> else if ('\0' == *str1&& '\0' == *str2)
> {
> ret = 1;
> }
> else
> {
> size_t len1 = strlen(str1);
> size_t len2 = strlen(str2);
> const char* tmp1 = str1 + len1 - 1;
> const char* tmp2 = str2 + len2 - 1;
> size_t count = 0;
> for(; *tmp1 == *tmp2&& count< len2; --tmp1, --tmp2, ++count)
> ;
>
> if(count == len2&& *++tmp1 == *++tmp2) ret = 1;
> else ret = 0;
> }
>
> return ret;
> }
>
> ==================== OUTPUT =========================
> [arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra strend.c
> [arnuld@dune C]$ ./a.out
> strend(comp.lang.c, comp.lang.) = 0
> [arnuld@dune C]$
>
>
>

--
Ian Collins

Ben Bacarisse

6/23/2011 12:29:00 PM

arnuld <sunrise@invalid.address> writes:

> K&r2, exercise 5-4, page 107
>
> Write the functions strend(s,t), which returns 1 if the string t occurs
> at the end of the string s, and zero otherwise.
<snip>
> /* return 1 if str2 occurs at the end of str1, zero otherwise */
> int strend(const char* str1, const char* str2)
> {
> int ret;
>
> /* If one of arguments is NULL, there is no pint in going next */
> if(NULL == str1 || NULL == str2)
> {
> ret = 0;
> }
> else if(strlen(str1) < strlen(str2))
> {
> ret = 0;
> }
> else if ('\0' == *str1 && '\0' == *str2)
> {
> ret = 1;
> }
> else
> {
> size_t len1 = strlen(str1);
> size_t len2 = strlen(str2);
> const char* tmp1 = str1 + len1 - 1;
> const char* tmp2 = str2 + len2 - 1;

Same error as I posted about in another thread. When either string is
"", the tmp1 or tmp2 pointer will be invalid.

> size_t count = 0;
> for(; *tmp1 == *tmp2 && count < len2; --tmp1, --tmp2, ++count)
> ;

And, you access the pointer. In fact, you do so for all matching
strings because the decrements will always take one of the tmp pointers
to before the start of the strings. You probably wanted test count
before you test anything else.

BTW, this is for loop abuse! I'd write this as a while loop.

> if(count == len2 && *++tmp1 == *++tmp2) ret = 1;
> else ret = 0;

This looks wrong but given that the previous loops is wrong I can't
really say exactly how. I think you intended, in the loop, to test
count first and then you'd need this extra test, but I am not sure.

I've found that "end" string processing is almost always clearer if you
point at the null:

const char* tmp1 = str1 + len1;

and you decrement before testing a character:

if (tmp1 > str1 && *--tmp1 == 'X') ...

etc. However, this is a case where you should use strcmp, rather than
rolling your own loop.

> }
>
> return ret;
> }

--
Ben.

Mark Bluemel

6/23/2011 1:08:00 PM

On 06/23/2011 11:56 AM, arnuld wrote:
> K&r2, exercise 5-4, page 107
>
> Write the functions strend(s,t), which returns 1 if the string t occurs
> at the end of the string s, and zero otherwise.

Your solution presupposes strlen(), so it may as well presuppose
strcmp(). If you don't already have them, write them as building blocks
for this...

As others have suggested one testcase doesn't prove much - even a
stopped clock is right twice a day.

Here's something I threw together.

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

int strend(const char* s1, const char* s2);

int main(void)
{
const char* arr1[] = { NULL,
"",
"comp.lang.c",
"comp.lang.perl",
"uk.fan.monkees"};
const char* arr2[] = { NULL,
"",
"comp.lang.",
"unutterablyLongString",
"lang.c",
"ees",
"l"
};
int i;
int j;

for (i = 0 ; i < (sizeof arr1/sizeof (char *)); i++) {
for (j = 0 ; j < (sizeof arr2/sizeof (char *)); j++) {
printf("strend(%s, %s) = %d\n", arr1[i], arr2[j], strend(arr1[i],
arr2[j]));
}
}

return 0;
}

/* return 1 if str2 occurs at the end of str1, zero otherwise */
int strend(const char* str1, const char* str2)
{
int str1_len;
int str2_len;
const char *comparison_start;

if ((str1 == NULL) || (str2 == NULL)) {
return 0;
}

str1_len = strlen(str1);
str2_len = strlen(str2);

if (str2_len == 0) {
return 0;
}

if (str2_len > str1_len) {
return 0;
}

comparison_start = str1 + str1_len - str2_len;
return !strcmp(comparison_start,str2);
}

Phil Carmody

6/23/2011 11:23:00 PM

Mark Bluemel <mark_bluemel@pobox.com> writes:
> /* return 1 if str2 occurs at the end of str1, zero otherwise */

This is pretty much what I'd do too, with a few tweaks.

> int strend(const char* str1, const char* str2)
> {
> int str1_len;
> int str2_len;

size_t is better.

> const char *comparison_start;
>
> if ((str1 == NULL) || (str2 == NULL)) {
> return 0;
> }
>
> str1_len = strlen(str1);
> str2_len = strlen(str2);
>
> if (str2_len == 0) {
> return 0;

Doesn't the empty string appear at the end of every string? Or did you mean
str1_len?

Either way, the calculation of the length you've not used yet can be
delayed until this point, so that some trivial cases can be handled
more quickly.

> }
>
> if (str2_len > str1_len) {

If you calculate str1_len first, then you can use a strnlen[*] rather than
strlen on str2, in order to be able to bail early on the above condition.

> return 0;
> }
>
> comparison_start = str1 + str1_len - str2_len;
> return !strcmp(comparison_start,str2);

Memcmp doesn't need to keep checking for '\0' characters, which you know
will be absent in the sections you're interested in comparing.

> }

Phil

[* GNU provides one for you, but you might need to write your own,
it's a strlen with a maximum length.]

--
"At least you know where you are with Microsoft."
"True. I just wish I'd brought a paddle." -- Matthew Vernon

Gene

6/24/2011 1:15:00 AM

On Jun 23, 7:22 pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
wrote:
> Mark Bluemel <mark_blue...@pobox.com> writes:
> > /* return 1 if str2 occurs at the end of str1, zero otherwise */
>
> This is pretty much what I'd do too, with a few tweaks.
>
> > int strend(const char* str1, const char* str2)
> > {
> > int str1_len;
> > int str2_len;
>
> size_t is better.
>
> > const char *comparison_start;
>
> > if ((str1 == NULL) || (str2 == NULL)) {
> > return 0;
> > }
>
> > str1_len = strlen(str1);
> > str2_len = strlen(str2);
>
> > if (str2_len == 0) {
> > return 0;
>
> Doesn't the empty string appear at the end of every string? Or did you mean
> str1_len?
>
> Either way, the calculation of the length you've not used yet can be
> delayed until this point, so that some trivial cases can be handled
> more quickly.
>
> > }
>
> > if (str2_len > str1_len) {
>
> If you calculate str1_len first, then you can use a strnlen[*] rather than
> strlen on str2, in order to be able to bail early on the above condition.
>
> > return 0;
> > }
>
> > comparison_start = str1 + str1_len - str2_len;
> > return !strcmp(comparison_start,str2);
>
> Memcmp doesn't need to keep checking for '\0' characters, which you know
> will be absent in the sections you're interested in comparing.
>
> > }

Another approach is to keep finding the first occurrence until you
find the last:

// UNCOMPILED; UNTESTED
int strend(const char* str1, const char* str2)
{
int len2;
char *p, *str2loc;

if (str1 && str2) {
len2 = strlen(str2);
// p points to the unsearched part of str1
p = str1;
for (;;) {
char *str2loc = strstr(p, str2);
if (!str2loc)
return 0;
p = str2loc + len2;
if (*p == '\0')
return 1;
}
}
return 0;
}

Ike Naar

6/24/2011 6:19:00 AM

On 2011-06-24, Gene <gene.ressler@gmail.com> wrote:
> // UNCOMPILED; UNTESTED
> int strend(const char* str1, const char* str2)
> {
> int len2;
> char *p, *str2loc;
>
> if (str1 && str2) {
> len2 = strlen(str2);
> // p points to the unsearched part of str1
> p = str1;
> for (;;) {
> char *str2loc = strstr(p, str2);
> if (!str2loc)
> return 0;
> p = str2loc + len2;
> if (*p == '\0')
> return 1;
> }
> }
> return 0;
> }

You mentioned that the code is uncompiled and untested, and in
fact it has a few compilation errors but they are easy to fix.

One "real" problem: the for loop does not terminate if str2
is the empty string.

Ike Naar

6/24/2011 6:59:00 AM

On 2011-06-24, Ike Naar <ike@sverige.freeshell.org> wrote:
> On 2011-06-24, Gene <gene.ressler@gmail.com> wrote:
>> // UNCOMPILED; UNTESTED
>> int strend(const char* str1, const char* str2)
>> {
>> int len2;
>> char *p, *str2loc;
>>
>> if (str1 && str2) {
>> len2 = strlen(str2);
>> // p points to the unsearched part of str1
>> p = str1;
>> for (;;) {
>> char *str2loc = strstr(p, str2);
>> if (!str2loc)
>> return 0;
>> p = str2loc + len2;
>> if (*p == '\0')
>> return 1;
>> }
>> }
>> return 0;
>> }
>
> You mentioned that the code is uncompiled and untested, and in
> fact it has a few compilation errors but they are easy to fix.

To Gene: Sorry about the phrase "a few compilation errors"; there's
only a single compilation error in the above fragment (the assigment
``p = str1'' assigns a pointer-to-const to a pointer-to-nonconst).

There was another compilation error, but that was in the code that
I added to turn your code fragment into a complete program.

Tim Rentsch

6/25/2011 5:08:00 PM

Mark Bluemel <mark_bluemel@pobox.com> writes:

> On 06/23/2011 11:56 AM, arnuld wrote:
>> K&r2, exercise 5-4, page 107
>>
>> Write the functions strend(s,t), which returns 1 if the string t occurs
>> at the end of the string s, and zero otherwise.
>
> Your solution presupposes strlen(), so it may as well presuppose
> strcmp(). If you don't already have them, write them as building
> blocks for this...
> [snip]
>
> /* return 1 if str2 occurs at the end of str1, zero otherwise */
> int strend(const char* str1, const char* str2)
> {
> int str1_len;
> int str2_len;
> const char *comparison_start;
>
> if ((str1 == NULL) || (str2 == NULL)) {
> return 0;
> }
>
> str1_len = strlen(str1);
> str2_len = strlen(str2);
>
> if (str2_len == 0) {
> return 0;
> }
>
> if (str2_len > str1_len) {
> return 0;
> }
>
> comparison_start = str1 + str1_len - str2_len;
> return !strcmp(comparison_start,str2);
> }

An alternative offered for everyone's reading pleasure
and/or amusement (as each may individually determine).

/* Return 1 if 'tail' occurs at the end of 'whole', or 0 if not. */

int
strend( const char *whole, const char *tail ){
size_t w, t;

return
whole && tail
&& (w = strlen( whole )) >= (t = strlen( tail ))
&& strcmp( whole+w -t, tail ) == 0
;
}

arnuld

6/27/2011 8:03:00 AM

> On Sat, 25 Jun 2011 10:07:44 -0700, Tim Rentsch wrote:

> An alternative offered for everyone's reading pleasure and/or amusement
> (as each may individually determine).
>
>
> /* Return 1 if 'tail' occurs at the end of 'whole', or 0 if not. */
>
> int
> strend( const char *whole, const char *tail ){
> size_t w, t;
>
> return
> whole && tail
> && (w = strlen( whole )) >= (t = strlen( tail )) && strcmp(
> whole+w -t, tail ) == 0
> ;
> }

Interesting :) , if we assume not to use any of those standard string
library functions (strcmp, strlen etc) then can we accomplish ?

--
www.lispmachine.wordpress.com
find my email-ID @above blog

Mark Bluemel

6/27/2011 8:07:00 AM

On 06/25/2011 06:07 PM, Tim Rentsch wrote:

> An alternative offered for everyone's reading pleasure
> and/or amusement (as each may individually determine).
>
>
> /* Return 1 if 'tail' occurs at the end of 'whole', or 0 if not. */
>
> int
> strend( const char *whole, const char *tail ){
> size_t w, t;
>
> return
> whole&& tail
> && (w = strlen( whole ))>= (t = strlen( tail ))
> && strcmp( whole+w -t, tail ) == 0
> ;
> }

Now if you'd used 'lo1' for "whole", "l0l" for "tail", "lol" for "w" and
"l01" for "t", it would have been even more perfect...

comp.lang.c

K&R2, exercise 5-4, strend(s,t

arnuld

Ian Collins

Ben Bacarisse

Mark Bluemel

Phil Carmody

Gene

Ike Naar

Ike Naar

Tim Rentsch

arnuld

Mark Bluemel

x Login to ForumsZone