How to debug this substring matching code?

Question

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.

Answer 1

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.

Answer 2

A wrong cases offered in comments: s = ababac, t = abac.

According to the logic of the original code, the pointer s should move back by a certain position each time in the else{} statement, but the original code overlooks it.

I rewrite it like :

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

it works.