PAT 甲級 10-2：字符串刪除所有子串（strstr + strcpy 陷阱與修正）

題目要求

• 輸入兩行字符串 S1、S2（長度 ≤ 80）
• 從 S1 中刪除所有出現的 S2 子串
• 輸出刪除後的 S1

樣例

S1: Tomcat is a male ccatat cat
S2: cat
輸出: Tom is a male  at

注意：ccatat 中含兩個重疊 cat？實際按左至右非重疊刪除。

初版代碼（存在 Bug）

char S1[81], S2[81];
gets(S1); gets(S2);
int len = strlen(S2);
char *p = strstr(S1, S2);
while (p) {
    strcpy(p, p + len);  // 危險：源/目標重疊未定義行為
    p = strstr(S1, S2);
}
printf("%s\n", S1);

問題分析

• strcpy 要求源目標不重疊，此處 p 與 p+len 重疊 → UB
• 應用 memmove（允許重疊）或手動後移

修正版

#include <stdio.h>
#include <string.h>

int main() {
    char S1[81], S2[81];
    gets(S1); gets(S2);
    int len = strlen(S2);
    char *p;
    while ((p = strstr(S1, S2)) != NULL) {
        memmove(p, p + len, strlen(p + len) + 1);  // 含結束符
    }
    printf("%s\n", S1);
    return 0;
}

關鍵點

• memmove 處理重疊內存移動，安全可靠
• strlen(p+len)+1 確保包含 \0 複製
• 循環條件直接賦值判斷，簡潔
• 輸入用 gets（題目保證無空行），實際工程建議 fgets

複雜度

最壞 O(|S1| * |S2|)，長度 ≤ 80 完全可接受。