K&R2, exercise 5.4

[Hallvard B Furuseth]

What gave you that idea? Yes it can. Try.

Let's give it a go:

char a[59] = "String 1";
(...)

Duh, of course. I was thinking "string literal", not "string".

 

[Anand Hariharan]

No. I dispute that "the empty string has size = 1", which is a different
statement entirely.

ITYM "I /contend/ that \"the empty string has size = 1\"". Or am I
splitting hairs here?

 

[arnuld]

In two hours you published six versions of this program. This is the
latest according to my news server but I have no idea if it is the
latest you published. Keeping the title the same is good but maybe
you should put a version number in the code.

ok here is the final working version


/* Exercise 5.4 from K&R2, page 107
*
* write the function strend(s, t) which returns 1 if the
* string t occurs at the end of string s and zero otherwise.
*
* Final-Version of code
*/


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

int strend( char*, char*, int );



int main( void )
{
int arrsize;
char s[] = "Love";
char t[] = "ve";

arrsize = (int) sizeof(t) / sizeof(char);

printf("\n%d\n", strend(s,t, arrsize));


return EXIT_SUCCESS;
}



int strend( char* s, char* t, int n )
{
char *ps, *pt;

for( ; *s != '\0'; s++ )
{
for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )
{
;
}

if( n > 1 && *pt == '\0' && *ps == '\0' )
{
return 1;
}

}

return 0;
}

 

[arnuld]

ok here is the final working version

The only thing I did not understand in my final version is if I remove
these 2 pieces of code:

1.) *pt != '\0' from inner <for> loop
2.) *pt == '\0' && *ps == '\0' , from <if> condition

then the program gives strange results


removing (1) will force code to compare for '\0' in the inner for loop and
hence there is no need to compare for NULL in <if> condition. Then why
program gives wrong results ?

 

[Ben Bacarisse]

The only thing I did not understand in my final version is if I remove
these 2 pieces of code:

1.) *pt != '\0' from inner <for> loop
2.) *pt == '\0' && *ps == '\0' , from <if> condition

then the program gives strange results


removing (1) will force code to compare for '\0' in the inner for loop and
hence there is no need to compare for NULL in <if> condition. Then why
program gives wrong results ?

You need to just work though what happens. Mod no 1 allows ps and pt
to run off the end of the strings. In fact, most string loops like
this are wrong:

for (<setup>; *s1 == *s2; s1++, s2++) <stuff>;

Why? Because you might look at the characters after the nulls and
there may be no such character -- anything at all might happen.

Mod 2 is just daft (sorry!). Regardless of whether you do 1 or not,
that just leaves: if (n > 1) so you return result simply depends on
getting into the loop at all and nothing at all about the strings.
See my other post about the n parameter.

 

[Ben Bacarisse]

ok here is the final working version

Not quite!

/* Exercise 5.4 from K&R2, page 107
*
* write the function strend(s, t) which returns 1 if the
* string t occurs at the end of string s and zero otherwise.
*
* Final-Version of code
*/

int strend( char* s, char* t, int n )

You need to loose the n. The question as posed (see above) can be
answered knowing only s and t. No further data is needed, so any
other parameters you give must come from some misunderstanding or the
problem.

{
char *ps, *pt;

for( ; *s != '\0'; s++ )
{
for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )
{
;
}

if( n > 1 && *pt == '\0' && *ps == '\0' )

Even when you loose the n, this test is over complex. Write down what
you know when the loop above ends.

 

[arnuld]

You need to loose the n. The question as posed (see above) can be
answered knowing only s and t. No further data is needed, so any
other parameters you give must come from some misunderstanding or the
problem.

ok, I removed "n". I have to use my_strlen - to find the length of the string:



/* Exercise 5.4 from K&R2, page 107
*
* write the function strend(s, t) which returns 1 if the
* striing t occurs at the end of string s and zero otherwise
*
* Final Version 2
*/


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

int strend( char*, char*);
int my_strlen( char* s);



int my_strlen( char* s )
{
char* ps;

ps = s;
while( *ps != '\0' )
{
++ps;
}

return ps - s;
}


int main( void )
{
char s[] = "Love";
char t[] = "ee";


printf("\n%d\n", strend(s,t));


return EXIT_SUCCESS;
}



int strend( char* s, char* t )
{
char *ps, *pt;
int len_of_t;

len_of_t = my_strlen( t );


for( ; *s != '\0'; s++ )
{
for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )
{
;
}

if( len_of_t && *pt == '\0' && *ps == '\0' )
{
return 1;
}

}

return 0;
}

Even when you loose the n, this test is over complex. Write down what
you know when the loop above ends.

<if> follows from the inner <for> loop:

for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )

lets say s = "Love" and t = "ee"

then *pt == *ps will go false and hence the NULL checking in the if condition
is required otherwise it will always print 1. I am not able to find a
replacement for this.

 

[Ben Bacarisse]

I meant "of the problem", but that was not one of my worst typos!

ok, I removed "n". I have to use my_strlen - to find the length of
the string:

That's one way, but having found the length you could put it to much
more use (I posted an outline elsewhere).

<if> follows from the inner <for> loop:

for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )

lets say s = "Love" and t = "ee"

then *pt == *ps will go false and hence the NULL checking in the if condition
is required otherwise it will always print 1. I am not able to find a
replacement for this.

I don't think I am wrong, but the logic is a bit hairy, so lets just
tabulate the cases:

*ps *pt *ps == *pt
0 0 0 logically impossible
0 0 1 match found
0 x 0 no match
0 x 1 logically impossible
x 0 0 no match
x 0 1 logically impossible
x y 0 impossible (loop won't have ended)
x x 1 impossible (loop won't have ended)

The last two can't occur because the loop won't have terminated.
Three other cases are not possible due to simple logic (e.g. in the
first line, if both *pt and *pt are 0 the last entry must be 1 not
0). That leaves:

*ps *pt *ps == *pt
0 0 1 match found
0 x 0 no match
x 0 0 no match

so you could just test *ps == *pt. What this means is that loop must
have ended because *pt == 0, so there is no point in test in both.
Now, I agree this not obvious, but when you start to think this way it
does become clearer. You would, absolutely, have to have a comment
saying:

if (*ps == *pt) {
/* The for loop must have ended because *pt == 0. */
return 1;
}

 

[Philip Potter]

int strend( char* s, char* t )
{
char *ps, *pt;
int len_of_t;

len_of_t = my_strlen( t );


for( ; *s != '\0'; s++ )
{
for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )
{
;
}

if( len_of_t && *pt == '\0' && *ps == '\0' )

You're saying that if t is length zero then it can't be the end of any
other string. I would argue that a string of length zero is /always/ the
end of another string.

If I have two nonempty strings a and b, and I know b is a suffix of a
(ie strcmp(&a,b) == 0 for some value of i), then surely if I chop a
character off the end of a and b then b will still be a suffix of a?

Similarly, if two strings are equal, then each is a suffix of the other.
Therefore "" is a suffix of "".

With all this in mind, you don't need a special case for the empty
string because it Just Works.

As Ben (and I) have said, you can use len_of_t to make a far more
efficient algorithm.