string question..

[transgalactic2]

i got two helping functions:


*FindFirst(char *str,char c) char

returns the pointer to a place in the given string when char c appears for the 1st time.


char *FindLast(char* str,char c, int n)

returns the pointer to a place in the given string when char c appears for the n ' th time.

i need to build a recursive only function
char*MinSubstring( char *str, int n, char c, int *len)

which returns a pointer to a place where a substring with the minimal length starts ,in
which char c appears for the n times.
parameter len should store the length of our found string.

i cant think of an algorithm to do that??

[itCbitC]

...
i cant think of an algorithm to do that??

Note that the minimal length substring will start and end with the character c.

[Adak]

Instead of thinking "What algorithm will do this?", I believe you should work the problem out by hand several times, and then you'll have learned an algorithm to do this problem.

The purpose is to make you sit down and figure out the problem by hand, and then put that solution into pseudo-code, (or a flow chart), and then translate that into code, function by function.

Asking for help before you even have learned how to do the problem by hand, just defeats the purpose of your learning, which is to learn how to solve these problems.

[transgalactic2]

i cant think of a general way

[quzah]

I'm pretty sure you haven't tried ANYTHING here. Take the first example. Show us your code how you'd search for a character in a string, and return the place where it is. Go.

Without any effort, we're not so inclined to "help" you.


Quzah.

[Adak]

i cant think of a general way

I can't think that you're trying when you show no evidence of working on this problem, at all.

You're not a raw beginner, anymore.

Get to work: first with pencil and paper, solving it by hand, then with pseudo code or flow charts, and then by building up the code, function by function.

[transgalactic2]

i am thinking of taking the first place of the string
and making FindLast(char* str,char c, int n)
then i substract the first place with the place which were returned and save the subtraction

then i compare the length with the length i will get from
MinSubstring(str+1, n, c,&len);

i save in len the minimal length

and return the place where the minimal string starts.

is there any problem in this code

char*MinSubstring( char *str, int n, char c, int *len)
{
	int length,next_length;
	
    char* place,next_place;
	
	place=FindLast(str,c,n);
	length=place-str;
	if (*str!='\0')
	next_place=MinSubstring(str+1,n,c,&next_length);
    if (next_length>length)
	{
      *len=length;
	  return place;
	}
	else
	{
       *len=next_length;
	  return next_place;
	}
}

[transgalactic2]

how to do flow chart on this problem?

[dwks]

is there any problem in this code

You mean other than the fact that next_length and next_place will be uninitialized if *str is in fact 0, and the fact that next_place is a char rather than a char*?

[transgalactic2]

how * str will be 0??

char*MinSubstring( char *str, int n, char c, int *len)
{
	int length,next_length;
	
    char* place;
	char *next_place
	place=FindLast(str,c,n);
	length=place-str;
	if (*str!='\0')
	next_place=MinSubstring(str+1,n,c,&next_length);
    if (next_length>length)
	{
      *len=length;
	  return place;
	}
	else
	{
       *len=next_length;
	  return next_place;
	}
}

i fixed what you said,any more logical problems?

[sean]

Well how does it behave when you run it? You should write a program that calls your function with a test string and displays the results. See what this function does, and then see what needs to change to fix any problems.

[dwks]

Here's your code indented so that I can read it. (Oh, and with a semicolon added so that it would have a better chance of compiling.)

char *MinSubstring( char *str, int n, char c, int *len)
{
    int length, next_length;
    
    char* place;
    char *next_place ;
    place=FindLast(str,c,n);
    length=place-str;
    
    if (*str!='\0')
        next_place=MinSubstring(str+1,n,c,&next_length);
    
    if (next_length>length)
    {
        *len=length;
        return place;
    }
    else
    {
        *len=next_length;
        return next_place;
    }
}

You say if (*str!='\0'), and then if that's the case you go on to set next_place and (presumably) next_length. But what if this if doesn't execute? i.e., what if *str == '\0'? (That's what I meant when I said "if *str is in fact 0". '\0' and 0 are the same thing.)

What will happen is that next_place and next_length won't have been assigned any values at all. They'll be uninitialized. But then you go and execute this:

    if (next_length>length)

Do you think that's going to work if next_length hasn't been assigned a value? Hint: not very well.

[transgalactic2]

char *MinSubstring( char *str, int n, char c, int *len)
{
    int length, next_length;
    
    char* place;
    char *next_place ;
    place=FindLast(str,c,n);
    length=place-str;
    
    if (*str=='\0')
       *next_length=9999999;
        return NULL;
    if (*str!='\0')
        next_place=MinSubstring(str+1,n,c,&next_length);
    
    if (next_length>length)
    {
        *len=length;
        return place;
    }
    else
    {
        *len=next_length;
        return next_place;
    }
}

now it solves the problem ?

[dwks]

Umm, no. Since you haven't put in curly braces, the "return NULL" always executes . . . .