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.
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
.