CODEWITHSUNDEEP
c++carraysalgorithmrecursion
Athamas
Athamas

Reputation: 611

Recursive algorithm for substrings of the same character in C

I'm trying to build a recursive algorithm that, starting from a string such as "xxxzzppp", will only return true if every sequence (continous substring) of the same character is made up of less or equals characters compared to the following one, up to the end.

It is assumed that a string is alphabetically ordered.

It will return 0 otherwise.

Example:

xxppp = 1;  // by = I mean that it should return that value when given to the function
xxxp = 0;
nnnpppz = 0;
npz = 1;
npp = 1;
llleeeegggg = 1;

I have tried this:

int CheckOcc(char seq[]) {
    int j = 0, counter = 0;

    if (strlen(seq) == 0)
        return 100;  //last is always shorter than nothing

    for (j = 0; j < strlen(seq); j++)
        if (seq[0] == seq[j])
            counter++;

    if (counter <= CheckOcc(seq + j))
        return counter;
    else
        return 0;

}

But I just can't get it to work, can anyone give a suggestion please? I have been over this for two hours and just can't figure it out.

EDIT:

Please note that by passing seq + j, I'm actually passing the stirng starting from the first substring after the one that has just ended. The pointer algebra is correct, I just can't figure out the algorithm, in particular, I do not know what to return. Any help is very appreciated.

Upvotes: 1

Views: 172

Answers (1)

BLUEPIXY
BLUEPIXY

Reputation: 40145

try this

#include <stdio.h>
#include <limits.h>

int CheckOcc(char seq[]) {
    int j = 0, counter = 0;

    if (!*seq) return INT_MAX;

    for (j = 0; seq[j] && *seq == seq[j]; j++)
        counter++;

    return (counter <= CheckOcc(seq + j)) ? counter : 0;
}
int main(void){
    char input[128];
    while(1 == scanf("%127[^\n]%*c", input)){
        if(CheckOcc(input))
            printf("%s = 1\n", input);
        else
            printf("%s = 0\n", input);
    }
    return 0;
}

Upvotes: 2

Related Questions