词语/短语替换程序超时问题求助（附完整C代码）

我正在完成一项大学编程任务，需要实现一个将“不良”短语替换为“合规”短语的函数。函数输入为文本和存储替换规则的二维数组（左列是待替换的不良词，右列是替换用的合规词，数组末尾以NULL-NULL结尾）。

关键要求：

• 程序不得修改已完成替换的内容，例如“termination specialist”中的“specialist”不应被再次替换；
• 需通过replaceInvalidity函数检查替换字典有效性：任意不良词不能是另一个不良词的前缀。

我的代码通过了大部分测试，但在某一测试用例中出现循环并超出2秒时间限制，导致任务得分为0。已经用Valgrind检查内存，未发现错误。完整代码如下：

#ifndef __PROGTEST__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>
#endif /* __PROGTEST__ */

int replaceInvalidity(const char * (*replace)[2])
{
    int size = 0;
    for (int i = 0; replace[i][0] != NULL; i++)
        size++;
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            if (strlen(replace[i][0]) >= strlen(replace[j][0]))
            {
                if (strstr(replace[i][0], replace[j][0]) == replace[i][0])
                    return 1;
            }
            else
            {
                if (strstr(replace[j][0], replace[i][0]) == replace[j][0])
                    return 1;
            }
        }
    }
    return 0;
}

char *newSpeak(const char *text, const char * (*replace)[2])
{
    if (replaceInvalidity(replace))
    {
        return NULL;
    }

    int i = 0, k = 0, flag= 0, Nlen = 0, Olen = 0, length = 0;
    char *result = (char *)malloc(sizeof(char));
    length = strlen(text);

    for (i = 0, k = 0; i < length; i++, k++)
    {
        flag = 0;
        for (int j = 0; replace[j][1] != NULL; j++)
        {
            if (strstr(&text[i], replace[j][1]) == &text[i])
            {
                Nlen = strlen(replace[j][1]);
                result = (char *)realloc(result, ((k + Nlen + 1) * sizeof(char)));
                for (int l = k; l < k + Nlen; l++)
                    result[l] = replace[j][1][l-k];
                i += Nlen - 1;
                k += Nlen - 1;
                flag = 1;
                break;
            }
        }

        if (flag) continue;

        for (int j = 0; replace[j][0] != NULL; j++)
        {
            if (strstr(&text[i], replace[j][0]) == &text[i])
            {
                Olen = strlen(replace[j][0]);
                Nlen = strlen(replace[j][1]);
                result = (char *)realloc(result, ((k + Nlen + 1) * sizeof(char)));
                for (int l = k; l < k + Nlen; l++)
                    result[l] = replace[j][1][l-k];
                i += Olen - 1;
                k += Nlen - 1;
                flag = 1;
                break;
            }
        }

        if (flag) continue;

        result = (char *)realloc(result, (k + 2) * sizeof(char));
        result[k] = text[i];
    }
    result[k] = '\0';
    return result;
}

#ifndef __PROGTEST__
int main(int argc, char * argv[])
{
    char *res;

    const char * d1[][2] = {
        { "murderer", "termination specialist" },
        { "failure", "non-traditional success" },
        { "specialist", "person with certified level of knowledge" },
        { "dumb", "cerebrally challenged" },
        { "teacher", "voluntary knowledge conveyor" },
        { "evil", "nicenest deprived" },
        { "incorrect answer", "alternative answer" },
        { "student", "client" },
        { NULL, NULL }
    };

    const char * d2[][2] = {
        { "fail", "suboptimal result" },
        { "failure", "non-traditional success" },
        { NULL, NULL }
    };

    res = newSpeak("dumb termination specialist.", d1);
    assert(!strcmp(res, "cerebrally challenged termination specialist."));
    free(res);
  
    res = newSpeak("The student answered an incorrect answer.", d1);
    assert(!strcmp(res, "The client answered an alternative answer."));
    free(res);

    res = newSpeak("He was dumb, his failure was expected.", d1);
    assert(!strcmp(res, "He was cerebrally challenged, his non-traditional success was expected."));
    free(res);

    res = newSpeak("The evil teacher became a murderer.", d1);
    assert(!strcmp(res, "The nicenest deprived voluntary knowledge conveyor became a termination specialist."));
    free(res);

    res = newSpeak("Devil's advocate.", d1);
    assert(!strcmp(res, "Dnicenest deprived's advocate."));
    free(res);

    res = newSpeak("Hello.", d2);
    assert(!res);

    return EXIT_SUCCESS;
}
#endif /* __PROGTEST__ */

问题根源分析 #

1. 超时/循环触发原因：原代码错误地优先检查合规词是否匹配原文本，这完全违背需求——我们只需要替换原文本中的不良词，而非处理原文本里的合规词。如果合规词恰好出现在原文本中，会导致错误的位置跳转，极端情况下引发无限循环或超时。
2. 未遵守“不修改已替换内容”规则：原逻辑混淆了原文本遍历和结果构建的节奏，没有保证替换后的内容不会被二次处理。
3. 内存效率低下：频繁调用realloc会产生内存碎片，且每次分配都要复制数据，大幅降低性能。

修复后的代码 #

#ifndef __PROGTEST__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>
#endif /* __PROGTEST__ */

int replaceInvalidity(const char * (*replace)[2])
{
    int size = 0;
    for (int i = 0; replace[i][0] != NULL; i++)
        size++;
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            const char *longer = strlen(replace[i][0]) >= strlen(replace[j][0]) ? replace[i][0] : replace[j][0];
            const char *shorter = strlen(replace[i][0]) < strlen(replace[j][0]) ? replace[i][0] : replace[j][0];
            if (strstr(longer, shorter) == longer)
                return 1;
        }
    }
    return 0;
}

// 辅助函数：预计算替换后的总长度，避免频繁realloc
static size_t calculateResultLength(const char *text, const char * (*replace)[2]) {
    size_t len = strlen(text);
    const char *ptr = text;
    while (*ptr) {
        int matched = 0;
        for (int j = 0; replace[j][0] != NULL; j++) {
            const char *bad = replace[j][0];
            size_t bad_len = strlen(bad);
            if (strstr(ptr, bad) == ptr) {
                // 替换后长度变化：减去不良词长度，加上合规词长度
                len += strlen(replace[j][1]) - bad_len;
                ptr += bad_len;
                matched = 1;
                break;
            }
        }
        if (!matched) {
            ptr++;
        }
    }
    return len + 1; // 加上字符串终止符的空间
}

char *newSpeak(const char *text, const char * (*replace)[2])
{
    if (replaceInvalidity(replace)) {
        return NULL;
    }

    size_t result_len = calculateResultLength(text, replace);
    char *result = (char *)malloc(result_len);
    if (!result) {
        return NULL;
    }

    char *res_ptr = result;
    const char *text_ptr = text;
    size_t text_len = strlen(text);

    while (text_ptr < text + text_len) {
        int matched = 0;
        // 遍历替换规则，匹配当前位置的不良词
        for (int j = 0; replace[j][0] != NULL; j++) {
            const char *bad = replace[j][0];
            size_t bad_len = strlen(bad);
            if (strstr(text_ptr, bad) == text_ptr) {
                // 复制合规词到结果
                strcpy(res_ptr, replace[j][1]);
                res_ptr += strlen(replace[j][1]);
                // 跳过原文本中已匹配的不良词，保证不会重复处理
                text_ptr += bad_len;
                matched = 1;
                break;
            }
        }
        if (!matched) {
            // 无匹配时复制原字符
            *res_ptr++ = *text_ptr++;
        }
    }
    *res_ptr = '\0';
    return result;
}

#ifndef __PROGTEST__
int main(int argc, char * argv[])
{
    char *res;

    const char * d1[][2] = {
        { "murderer", "termination specialist" },
        { "failure", "non-traditional success" },
        { "specialist", "person with certified level of knowledge" },
        { "dumb", "cerebrally challenged" },
        { "teacher", "voluntary knowledge conveyor" },
        { "evil", "nicenest deprived" },
        { "incorrect answer", "alternative answer" },
        { "student", "client" },
        { NULL, NULL }
    };

    const char * d2[][2] = {
        { "fail", "suboptimal result" },
        { "failure", "non-traditional success" },
        { NULL, NULL }
    };

    res = newSpeak("dumb termination specialist.", d1);
    assert(!strcmp(res, "cerebrally challenged termination specialist."));
    free(res);
  
    res = newSpeak("The student answered an incorrect answer.", d1);
    assert(!strcmp(res, "The client answered an alternative answer."));
    free(res);

    res = newSpeak("He was dumb, his failure was expected.", d1);
    assert(!strcmp(res, "He was cerebrally challenged, his non-traditional success was expected."));
    free(res);

    res = newSpeak("The evil teacher became a murderer.", d1);
    assert(!strcmp(res, "The nicenest deprived voluntary knowledge conveyor became a termination specialist."));
    free(res);

    res = newSpeak("Devil's advocate.", d1);
    assert(!strcmp(res, "Dnicenest deprived's advocate."));
    free(res);

    res = newSpeak("Hello.", d2);
    assert(!res);

    return EXIT_SUCCESS;
}
#endif /* __PROGTEST__ */

修复说明 #

1. 移除错误的合规词匹配逻辑：删掉原代码中优先检查合规词的循环，只保留不良词替换逻辑，从根源避免错误匹配和循环。
2. 预计算结果长度：新增calculateResultLength函数，先遍历文本计算替换后的总长度，一次性分配内存，彻底解决频繁realloc的性能问题。
3. 严格遵守遍历规则：使用text_ptr仅遍历原文本，替换时直接跳过对应长度的原文本内容，保证已替换的结果内容不会被二次处理。
4. 简化前缀检查逻辑：优化replaceInvalidity函数的代码结构，逻辑更清晰，功能保持不变。

内容的提问来源于stack exchange，提问作者w.ilia.m