cif-statementpointerswhile-loopc-strings

How to debug this substring matching code?


I am a beginner in C programming, and this is a string matching code I wrote. It aims to find the positions where the substring t appears in the string s and print them. The use of pointers is required.This code scored 94 out of 100 in the OJ test.

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

int main () {
    char *s = malloc(100005);
    char *t = malloc(100005);

    scanf ("%s%s", s, t);

    char *ptrS = s;
    char *ptrT = t;

    if (s == NULL) {
        free(t);
        return 1;
    }
    if (t == NULL) {
        free(s);
        return 1;
    }

    while ( *ptrS != '\0') {
        if (*ptrT == *ptrS) {
            ptrT++;
            ptrS++;
        } else if (*ptrS != *(ptrT = t)) {
            ptrS++;
        }

        if (*ptrT == '\0') {
            printf("%d ", (ptrS - s) - (ptrT - t));
            ptrS = ptrS - (ptrT - t) + 1;
            ptrT = t;
        }
    }

    free(t);
    free(s);

    return 0;
}

I have tried many test cases that I could think of, and it gives the correct results for all of them. I hope to find any bugs or any test cases that cause it to error.


Solution

  • There are several logical errors in your code.

    The first one is that before using the function scanf you shall check that pointers s and t are not null pointers that is that memory for the character arrays was successfully allocated.

    You could write for example

    char *s = NULL;
    char *t = NULL;
    
    if ( ( s = malloc( 100005 ) ) != NULL && ( t = malloc( 100005 ) ) != NULL )
    {
        // process the arrays
    }
    
    free( t );
    free( s );
    

    In the call of scanf you should specify the field width like

    if ( scanf( "%100004s %100004s", s, t ) == 2 )
    {
        // process the inputed strings
    }
    

    The inner if statement in the else part of this if statement

    if (*ptrT == *ptrS) {
        ptrT++;
        ptrS++;
    } else if (*ptrS != *(ptrT = t)) {
        ptrS++;
    }
    

    must be written for example like

    if (*ptrT == *ptrS)
    {
        ptrT++;
        ptrS++;
    }
    else if ( *ptrT != '\0' )
    {
        ptrS = ptrS - ( ptrT - t ) + 1;
        ptrT = t;
    }
    
    if (*ptrT == '\0')
    {
        printf( "%td ", ( ptrS - s ) - ( ptrT - t ) );
    
        ptrS = ptrS - ( ptrT - t ) + 1;
        ptrT = t;
    }
    

    That is the logic of the assignment of the pointer PtrS must be the same as inside this if statement

    if (*ptrT == '\0') {
        printf("%d ", (ptrS - s) - (ptrT - t));
        ptrS = ptrS - (ptrT - t) + 1;
        ptrT = t;
    }
    

    Bear in mind that there is a duplicated code in your program.

    Difference of two pointers has type ptrdiff_t. So you need to use length modifier t in the format string of the call of printf

    printf("%td ", (ptrS - s) - (ptrT - t));
            ^^^
    

    And after the while loop you should insert the following call

    putchar( '\n' );
    

    Using such expressions like for example that

    (ptrS - s) - (ptrT - t)
    

    makes your code difficult to read. Usually such codes contain bugs as a rule.

    Instead of your while loop I would write something like the following

    for ( const char *ptrS = s; *ptrS != '\0'; ++ptrS )
    {
        if ( *ptrS == *t )
        {
            const char *ptrT = t;
    
            while ( *ptrT != '\0' && *ptrT == *( ptrS + ( ptrT - t ) ) )
            {
                ++ptrT;
            }
    
            if ( *ptrT == '\0' )
            {
                printf( "%td ", ptrS - s );
            }
        }
    }
    
    putchar( '\n' );
    

    Within the loops there are used pointers to const char because the loops do not change the processed strings.

    Pay attention to that instead of manually written loops you could use standard C function strstr together with strchr. And you could initially check that the length of the string stored in the array pointed to by the pointer s is not less than the length of the string stored in the array pointed to by the pointer t.