字符過濾器：根據過濾表移除字符串中指定字符的算法實現

問題描述

輸入字符串 str 和過濾表 s（長度均 ≤ 70），移除 str 中所有出現在 s 中的字符，輸出過濾後結果。

算法思路

對過濾表中每個字符，掃描主串構建新串：

1. 外層循環遍歷過濾表字符 b[i]
2. 內層掃描當前主串 a，非目標字符複製到臨時陣列 c
3. 將 c 複製回 a，更新長度 n
4. 最終 c 即為結果

時間複雜度 O(m×n)，m,n≤70 完全足夠。

代碼實現

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

int main() {
    int i, j, l, n, m;
    char a[70], b[70], c[70];

    gets(a);
    gets(b);
    n = strlen(a);
    m = strlen(b);

    for (i = 0; i < m; i++) {
        l = 0;
        for (j = 0; j < n; j++) {
            if (a[j] != b[i])
                c[l++] = a[j];
        }
        c[l] = '\0';
        for (j = 0; j < l; j++) a[j] = c[j];
        n = l;
        a[n] = '\0';
    }

    for (i = 0; c[i]; i++) printf("%c", c[i]);
    return 0;
}

優化方案

建立 256 大小的布爾查找表，標記過濾字符，單次掃描主串即可完成，複雜度降為 O(n+m)。

測試樣例

輸入：

asf$$a sf$$
$a

輸出： sf sf

移除所有 'a' 和 '$' 字符。