ccharsubstringc-stringscyclic

Count frequencies of string - using only stdio.h - C


We have got some exercise in C (We must use only stdio.h library):

Write a function that receives two strings and returns the number of occurences of the second in the first one, there could be overlapping dependent on cyclic parameter.

But I don't succeed treat the case of isCyclic is turned on.

for example if isCyclic is other than 0 and:

char *str1 = "aaa"; char *str2 = "aa"; We have to return 3

What is my mistake in isCyclic?..

Here is my implementation:

int strLength(const char *str) {
    int count = 0;

    while (*str) {
        count++;
        str++;
    }

    return count;
}

unsigned int countPatInStr(const char *str1, const char *str2, int isCyclic)
{
    int patternSize = strLength(str2);
    int textSize = strLength(str1);
    int res = 0;
    int j;

    if (isCyclic) { // Here is the case when overlapping is needed
        if (patternSize > textSize) {
            for (int i = 0; i < patternSize - textSize; i++) {
                for (int j = 0; j < textSize; j++) {
                    if (str1[j] != str2[i + j]) {
                        break;
                    }

                    if (j == textSize && i + j < patternSize) {
                        str2 += i + j;
                    } else if (j == textSize && i + j == patternSize) {
                        res++;
                    }
                }
            }
            return 0;
        }
    } else {
        /* A loop to slide pat[] one by one */
        for (int i = 0; i <= textSize - patternSize; i++) {
            /* For current index i, check for pattern match */
            for (j = 0; j < patternSize; j++) {
                if (str1[i + j] != str2[j]) {
                    break;
                }
            }

            // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
            if (j == patternSize) {
                res++;
            }
        }
        return res;
    }

    return 0;
}

Solution

  • Your function at least is invalid because in this loop

    for (int i = 0; i < patternSize - textSize; i++) 
    

    the condition can be equal to false. So the loop is never executed.

    And in this loop

                for (int j = 0; j < textSize; j++) {
                    if (str1[j] != str2[i + j]) {
                        break;
                    }
    

    there is used the index j with the pointer str1 and the index i + j with the pointer str2 when isCyclic is non-zero.

    The function can be written much simpler as it is shown in the demonstrative program below.

    #include <stdio.h>
    
    size_t strLength( const char *s )
    {
        size_t n = 0;
    
        for ( ; *s; ++s ) ++n;
    
        return n;
    }
    
    size_t countPatInStr( const char *s1, const char *s2, _Bool isCyclic )
    {
        size_t count = 0;
    
        size_t n1 = strLength( s1 );
        size_t n2 = strLength( s2 );
    
    
        if ( !( n1 < n2 ) || isCyclic )
        {
            size_t n = isCyclic ? n1 : n1 - n2 + 1;
            size_t divident = isCyclic ? n : n1;
    
            for ( size_t i = 0; i < n; i++ )
            {
                size_t j = 0;
                while ( j < n2 && s1[ ( i + j ) % divident] == s2[j] ) j++;
    
                count += j == n2;
            }
        }
    
        return count;
    }
    
    int main(void) 
    {
        const char *s1 = "aaa";
        const char *s2 = "aa";
    
        printf( "%zu\n", countPatInStr( s1, s2, 0 ) );
        printf( "%zu\n", countPatInStr( s1, s2, 1 ) );
    
        return 0;
    }
    

    The program output is

    2
    3
    

    Or if s1 and s2 are defined like

    const char *s1 = "aa";
    const char *s2 = "aaa";
    

    then the output will be

    0
    2
    

    Or if they are defined like

    const char *s1 = "abcabc";
    const char *s2 = "abc";
    

    then the output is

    2
    2
    

    Is it what you need?