如何调试这个子串匹配代码？

Question

我是C编程初学者，这是我写的字符串匹配代码。其目的是找到子串t在字符串s中出现的位置并打印出来。需要使用指针。此代码在 OJ 测试中得分为 94 分（满分 100 分）。

#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;
}

我尝试了很多我能想到的测试用例，它给出了所有测试用例的正确结果。我希望找到任何错误或任何导致错误的测试用例。

Answer 1

您的代码中有几个逻辑错误。

第一个是在使用函数

scanf

之前，您应该检查指针

s

和

t

不是空指针，即字符数组的内存已成功分配。

你可以写例如

char *s = NULL;
char *t = NULL;

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

free( t );
free( s );

在 scanf 的调用中，您应该指定字段宽度，例如

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

该 if 语句的 else 部分中的内部 if 语句

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

必须写成

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

这就是指针赋值的逻辑

PtrS

一定要和这个if语句里面一样

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

两个指针的差异具有类型

ptrdiff_t

。因此，您需要在调用

t

 的格式字符串中添加长度修饰符 

printf

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

在 while 循环之后，您应该插入以下调用

putchar( '\n' );

使用这样的表达方式，例如

(ptrS - s) - (ptrT - t)

使您的代码难以阅读。通常，此类代码通常包含错误。

我会编写以下代码，而不是 while 循环

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 );
        }
    }
}

请注意，您可以使用标准 C 函数

strstr

，而不是手动编写循环。并且您可以首先检查指针

s

所指向的数组中存储的字符串的长度是否小于指针

t

所指向的数组中存储的字符串的长度。