#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2012
    Posts
    7
    Rep Power
    0

    Can't work my way around pointers here


    Hi guys..
    This is the code i've written for strend() defined as:-
    C Code:
    int strend(char* s, char* t);


    This function returns 1 if the string t occurs at the end of the string s and 0 if not.

    Here is my code:


    C Code:
    #include <stdio.h>
     
    int strend(char* , char* );
     
    int main() {
     
    	char s[] = "mabababcabc";
    	char t[] = "abc";
    	printf("%d", strend(s,t));
     
    	return 0;
    }
     
    int strend(char* s, char* t) {
    /* <b>tcp</b> stores the address of the first element of string <b>t</b> */
    	char *tcp = t, *pos;
     
    	for(; *s; pos = ++s) {
    		//check for string match
    		while(*s == *t) {
    			s++;
    			t++;
     
    			if(*s == '\0')
    				return 1;
    		}
     
    		t = tcp;
    		s = pos;
    	}
     
    	return 0;
    }


    This code returns 0 even though the input should return 1. A dry run of the code seems to be correct.

    Please help.
    Thanks in advance.
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,961
    Rep Power
    481

    improve your "dry run". Keep this invalid code away from my computer.


    In
    if(0 == *s)

    What if at the same time 0 == *t ? Then you'd have a match. This line instead improves your example result:

    if(!(*s) && (*t)) return 1;

    Never mind. You didn't initialize pos . Your program is wrong wrong wrong. Don't feel badly, I love you all the same.

    Now look. Is your comment (found in your post, not the code) accurate?
    This function returns 1 if the string t occurs at the end of the string s and 0 if not.
    Do you care the strings match anywhere else? Your code sort of indicates that you care, which absolutely disagrees with the remark.

    If you intend to look for a match at "the left end" then check from the left end only. If, on the other hand, you only care about matches on "the right end" then you need to check backward from s[strlen(s)-1] and from t[strlen(t)-1] making sure that your index is non-negative.

    Don't worry, you're both lovable and charming. But as written, your program can overrun t because it lacks a test that the remainder of s is at least as long as t.

    Rethink, rewrite, test more cases.

    *capable. You're capable. Charming unknown to me.
    Last edited by b49P23TIvg; July 6th, 2012 at 04:04 PM. Reason: wording change
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,242
    Rep Power
    2222
    I concur with b49P23TIvg. I think you're trying to make your function overly complex.

    Now, this is mainly my training and work experience talking here, but I would be inclined to use a finite state machine, which are commonly implemented with a switch statement. Based on the input, you transition from one state to another, such that the particular state that you find yourself in effectively "remembers" how you got there. We use them all the time to parse input streams from serial ports, part of which function is to detect the start-character sequence of the message being received.

    For example with the general problem of finding a substring in a string (your condition of it having to be on the end renders your problem trivial, as b49P23TIvg has pointed out), the initial state would be "no match" so its action is to test the next character of s against the first character of t. If there is a match, then you transition to the second state, "one match"; else you do not transition. BTW, in each iteration through the machine, the input is the next character in s (so to implement it the switch would be inside a for-loop). In the "one match" state, you compare the next character of s to the second character of t, stepping to the "two match" state if they match. Otherwise, you'd test whether it's matching the first character of t, in case a new substring is starting; if not, then you transition back to the initial "no match" state. Once you reach the "all match" state, then you can return reporting having found a match.

    A handy thing about FSMs is how you design them. You sketch a diagram of states and transition edges connecting them. If you're in school, you'll get this theory in your 3rd or 4th year, especially in compiler design because this is what parsers use.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2012
    Posts
    7
    Rep Power
    0
    @b49P23TIvg
    About that *t being equal to 0, that is the point you know.
    The condition
    while(*s == *t) {--}
    checks that both characters are equal and
    if(*s == '\0') checks
    that the string s ends along with t (if they don't end together, then the match is found somewhere in between, which is not what i want. So it is ignored).
    Thus ur statement
    if(!(*s) && (*t)) return 1; will NOT let it return 1 when s ends after getting a match with t (at the end of string).

    Also it is the "right end" that is considered. For that i could have
    started from ( srtlen(s) -1 ) but i thought this code is cleaner and smarter.. :) . Dont judge me.

    The most important thing you pointed out was *pos not being initialized. As soon as i did that, the code rendered output correctly as expected. This mistake was pretty foolish, i know.

    The code was all wrong wrong wrong.. i know. Hence i asked for help you know. Thanks for you gesture.

    Comments on this post

    • b49P23TIvg agrees : Ooops, I misread the desired output and thought it was to return 0 on success, 1 on failure.
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,961
    Rep Power
    481
    Code:
    int main() {
        char
          *s = "mabababcabc",
          *t = "mabababcabcmabababcabc",
          *u = "the",
          *v = "abc";
        printf("%d%d%d\n", strend(s,t),strend(s,u),strend(s,v));
        return 0;
    }
    This main program prints the line
    101

    Is that what you intend? (I initialized
    pos=s;
    in strend)


    Note that the FSM is a built in function of j.
    Last edited by b49P23TIvg; July 6th, 2012 at 05:03 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2012
    Posts
    7
    Rep Power
    0
    b49P23TIvg

    About those outputs..
    *u = "the" which is not what *s ends with. Hence 0.
    *v = "abc" which is what *s ends with. Hence 1.
    For any variable,
    *w = "bca" which is present in *s but doesn't end with it, the o/p is 0.
    The code works fine until your input of *t was given.
    The mistake, i found, was, in the positioning of the condition checking (*s == '\0'). I have now put it before incrementing s and t. Now the code is working fine again. :)
    For,
    *t = "mabababcabcmabababcabc" the o/p is 0 as string
    *s = "mabababcabc" can't end with a string bigger than itself.

    Code:
    for(; *s; pos = ++s) {
    		//check for string match
    		while(*s == *t) {
    			if(*s == '\0')
    				return 1;
    			s++;
    			t++;
    		}
    
    		t = tcp;
    		s = pos;
    	}
    Thank you so much for pointing out the mistake. And i will be more careful posting things in the future.

    Regards,
    Mrigank.

IMN logo majestic logo threadwatch logo seochat tools logo