字符串子串出现次数统计：本地与在线运行结果不一致排查

问题描述 #

给定字符串T和模式字符串P，需统计P在T中的出现次数。输入规则：第一行是模式串P（长度≤10^{5），第二行是目标串T（长度≤10}6），输出P在T中的出现次数。

用户提供的C语言代码在本地运行时，输入P为Pham Q Dung、T为指定长字符串时输出10，但在线评测平台输出9，结果不一致，需排查原因。

代码实现 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 5000000
int Count(char T[], char P[])
{
    int count = 0;
    char *pos, *t;
    int index;
    t = &T[0];

    while ((pos = strstr(T, P)) != NULL)
    {
        index = pos - t;
        strcpy(T, T + index + 1);
        count++;
    }
    return count;
}
int main()
{
    char *T = (char *)malloc(N);
    char *P = (char *)malloc(N);
    fgets(P, N, stdin);
    fgets(T, N, stdin);
    if (P[strlen(P) - 1] == '\n')
        P[strlen(P) - 1] = '\0';
    if (T[strlen(T) - 1] == '\n')
        T[strlen(T) - 1] = '\0';
    int count = Count(T, P);
    printf("%d", count);
    return 0;
}

测试输入 #

• 模式串P：Pham Q Dung
• 目标串T：cdefghijkmlnoPham Q Dungxyz 1234567890Pham Q Dungijkmlnopqrstuvwxyz 1234567890Pham Q Dunghijkmlnopqrstuvwxyz 1234567890Pham Q Dungfghijkmlnopqrstuvwxyz 123456789Pham Q DungefghijkmlnopqrstuvwxyzPham Q DunghijkmlnopqrstuvwxyPham Q Dung67890Pham Q DungbcdefghijkmlnopqrstuvwPham Q Dungqrstuvwxyz 1234567890Pham Q Dung

问题原因分析 #

代码核心错误集中在Count函数的逻辑实现：

1. 指针偏移计算错误：t固定指向原字符串首地址，但每次执行strcpy(T, T + index + 1)后，T指向的内存内容被覆盖，后续pos - t计算的偏移量基于原字符串首地址，而非当前T的实际起始位置，导致字符串截断位置错误。
2. 截断逻辑错误：找到匹配后仅跳过1个字符（index + 1），而非跳过整个模式串长度，可能导致重叠匹配计数错误，或因错误截断丢失后续匹配项。
3. 修改原字符串风险：直接通过strcpy修改原字符串，可能因内存覆盖导致未定义行为，不同环境下内存布局差异会引发结果不一致。

修复后的代码 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 5000000

int Count(char T[], char P[])
{
    int count = 0;
    char *pos = T;
    int len_p = strlen(P);
    if (len_p == 0) return 0;

    while ((pos = strstr(pos, P)) != NULL)
    {
        count++;
        pos += len_p; // 跳过整个模式串，避免重叠匹配（需重叠则改为pos+1）
    }
    return count;
}

int main()
{
    char *T = (char *)malloc(N);
    char *P = (char *)malloc(N);
    if (!T || !P) {
        fprintf(stderr, "Memory allocation failed\n");
        return 1;
    }

    fgets(P, N, stdin);
    fgets(T, N, stdin);

    size_t len_p = strlen(P);
    if (len_p > 0 && P[len_p - 1] == '\n')
        P[len_p - 1] = '\0';
    size_t len_t = strlen(T);
    if (len_t > 0 && T[len_t - 1] == '\n')
        T[len_t - 1] = '\0';

    int count = Count(T, P);
    printf("%d\n", count);

    free(T);
    free(P);
    return 0;
}

修复说明 #

1. 修正查找逻辑：用pos指针从当前匹配位置的下一个模式串长度处继续查找，无需修改原字符串，避免内存覆盖和指针偏移错误。
2. 添加边界处理：检查空模式串、内存分配失败的情况，提升代码健壮性。
3. 释放内存：避免内存泄漏，符合C语言规范。

内容的提问来源于stack exchange，提问作者fknoob