C/C++ 字符串處理核心技法大全：回文判斷、逆序、統計、查找、循環移位、最長對稱子串

前言

字符串操作是面試高頻考點與工程基礎功。本文整理 7 道經典問題，提供指針/數組雙版本實現，涵蓋邊界處理、時間複雜度優化與實戰技巧。

1. 判斷回文串

雙指針頭尾向中間收斂比較，O(n) 時間、O(1) 空間。

bool isHuiwen(const char* str) {
    if (!str) return false;
    const char* p = str;
    const char* q = str + strlen(str) - 1;
    while (p < q) {
        if (*p++ != *q--) return false;
    }
    return true;
}

2. 字符串原地逆序

頭尾交換，指針或下標均可。

char* inverseString(char* str) {
    if (!str) return nullptr;
    char* p = str;
    char* q = str + strlen(str) - 1;
    while (p < q) swap(*p++, *q--);
    return str;
}

3. 統計最高頻字符（假設 ASCII 可見字符）

用 256 長度計數數組，單次遍歷 O(n)。

char maxCountChar(const char* str) {
    int cnt[256] = {0};
    char maxCh = 0; int maxCnt = 0;
    for (const char* p = str; *p; ++p) {
        if (++cnt[(unsigned char)*p] > maxCnt) {
            maxCnt = cnt[(unsigned char)*p];
            maxCh = *p;
        }
    }
    return maxCh;
}

4. 子串出現次數（朴素匹配，含重疊）

雙層循環 + 計數器，O(m·n)。工程上建議用 KMP/BM 算法優化至 O(m+n)。

int subNum_string(const char* src, const char* sub) {
    int n = strlen(src), m = strlen(sub), cnt = 0;
    for (int i = 0; i <= n - m; ++i) {
        int j = 0;
        for (; j < m; ++j)
            if (src[i+j] != sub[j]) break;
        if (j == m) ++cnt;
    }
    return cnt;
}

5. 字符串循環右移 n 位

三步翻轉法：整體逆序 → 前 n 逆序 → 後 n 逆序。O(n) 時間、O(1) 空間，無需額外緩衝區。

void loopMoveNum(char* str, int k) {
    if (!str) return;
    int len = strlen(str);
    k %= len;
    reverse(str, str + len);
    reverse(str, str + k);
    reverse(str + k, str + len);
}

6. 最長對稱子串（回文子串）

中心擴展法 O(n²) 或 Manacher 算法 O(n)。此處給出生成所有子串 + 回文驗證的簡明版（教學用）。

char* maxLenHuiwen(char* str) {
    int len = strlen(str);
    for (int L = len; L >= 2; --L)          // 從長到短枚舉長度
        for (int i = 0; i <= len - L; ++i) { // 枚舉起始位置
            char* sub = new char[L+1];
            strncpy(sub, str + i, L);
            sub[L] = '\0';
            if (isHuiwen(sub)) return sub;   // 找到最長即返回
            delete[] sub;
        }
    return nullptr;
}

7. 統計所有對稱子串個數及最長者

雙層枚舉所有子串，驗證回文並計數。

int countHuiwen(const char* str) {
    int len = strlen(str), cnt = 0;
    for (int L = 2; L <= len; ++L)
        for (int i = 0; i <= len - L; ++i) {
            char* sub = new char[L+1];
            strncpy(sub, str + i, L);
            sub[L] = '\0';
            if (isHuiwen(sub)) {
                ++cnt;
                cout << "對稱串: " << sub << " 位置: " << i << " 長度: " << L << endl;
            }
            delete[] sub;
        }
    return cnt;
}

測試主函數

int main() {
    char s1[] = "heehee";
    cout << "是否回文: " << isHuiwen(s1) << endl;
    inverseString(s1);
    cout << "逆序: " << s1 << endl;
    cout << "最高頻: " << maxCountChar(s1) << endl;
    cout << "子串 'he' 次數: " << subNum_string("hahahanihaohah", "hah") << endl;
    loopMoveNum(s1, 2);
    cout << "循環右移2: " << s1 << endl;
    char* p = maxLenHuiwen(s1);
    if (p) cout << "最長對稱: " << p << endl;
    countHuiwen(s1);
    return 0;
}

避坑指南

• 指針運算時注意 `const` 正確性，必要時 `const_cast` 或拷貝；
• 字符作數組下標必須轉 `unsigned char` 避免負索引；
• 動態分配內存務必配對 `delete[]`，或改用 `std::string`/`std::vector` 現代 C++ 風格；
• 海量數據場景必須替換為 KMP、Manacher、後綴自動機等線性/近線性算法。