C 語言計算兩字符串交集：位圖法 O(n+m) 高效實現

題目：輸入兩字符串，輸出兩者共有字符 (交集)，如 A="Marginle", B="Valaienie" → 輸出 aie (順序不限)。

算法思路：字符出現位圖

1. 建立兩個長度 256 的 bool 陣列 mapA, mapB，初始化為 0。
2. 遍歷字符串 A，將對應 ASCII 碼位置置 1。
3. 遍歷字符串 B，同理置 1。
4. 遍歷 0~255，若 mapA[i] && mapB[i] 則輸出 (char)i。

時間複雜度 O(n+m+256)，空間 O(256)，極其高效。

完整 C 代碼

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

int main() {
    char strA[1024], strB[1024];
    int mapA[256] = {0}, mapB[256] = {0};

    printf("輸入字符串 A: ");
    fgets(strA, sizeof(strA), stdin);
    strA[strcspn(strA, "\n")] = 0;  // 去換行

    printf("輸入字符串 B: ");
    fgets(strB, sizeof(strB), stdin);
    strB[strcspn(strB, "\n")] = 0;

    for (char *p = strA; *p; p++) mapA[(unsigned char)*p] = 1;
    for (char *p = strB; *p; p++) mapB[(unsigned char)*p] = 1;

    printf("交集字符: ");
    for (int i = 0; i < 256; i++) {
        if (mapA[i] && mapB[i]) putchar(i);
    }
    putchar('\n');
    return 0;
}

運行示例

輸入字符串 A: Marginle
輸入字符串 B: Valaienie
交集字符: aeiln

輸出順序按 ASCII 碼遞增 (a e i l n)，題目示例 aie 為任意順序均可。

變體：保留首次出現順序

// 遍歷 A，若在 B 中存在且未輸出過則輸出
int printed[256] = {0};
for (char *p = strA; *p; p++) {
    unsigned char c = *p;
    if (mapB[c] && !printed[c]) {
        putchar(c);
        printed[c] = 1;
    }
}

C++ STL 簡潔寫法

#include <bits/stdc++.h>
using namespace std;
int main() {
    string a, b; cin >> a >> b;
    vector va(256), vb(256);
    for (char c : a) va[c] = true;
    for (char c : b) vb[c] = true;
    for (int i = 0; i < 256; i++) if (va[i] && vb[i]) cout << char(i);
    cout << endl;
}

位圖法是字符集較小 (ASCII/擴展 ASCII) 時字符串交集的最優解。