您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

面試必考字串專題：十五大經典演算法完整解析與C++實作

編輯：關於C

字串演算法面試全景圖

字串處理是面試高頻考點，本文系統整理 15 大經典問題，涵蓋轉換、查找、匹配、回文、排列等核心類型，附帶 C++ 實作與複雜度分析。

一、字串與數值互轉

atoi：字串轉整數 (完整版)


int myatoi(const char *str) {
    if (!str) return 0;
    while (*str == ' ' || *str == '\t') str++;  // 跳過空白
    
    int sign = 1;
    if (*str == '-') { sign = -1; str++; }
    else if (*str == '+') str++;
    
    long long result = 0;  // 用長整型防溢位檢測
    while (*str >= '0' && *str <= '9') {
        result = result * 10 + (*str - '0');
        if (sign == 1 && result > INT_MAX) return INT_MAX;
        if (sign == -1 && -result < INT_MIN) return INT_MIN;
        str++;
    }
    return sign * result;
}

itoa：整數轉字串


void itoa_mf(int num, char *str) {
    int sign = num;
    int i = 0;
    char temp[32];
    
    if (num < 0) num = -num;
    do {
        temp[i++] = num % 10 + '0';
        num /= 10;
    } while (num > 0);
    
    if (sign < 0) temp[i++] = '-';
    temp[i] = '\0';
    
    // 反轉
    int j = 0;
    while (i > 0) str[j++] = temp[--i];
    str[j] = '\0';
}

二、最長相同字元子串


char* GetLongestSameCharSubstr(const char *s) {
    int n = strlen(s), maxLen = 1, maxPos = 0;
    int curLen = 1, curPos = 0;
    
    for (int i = 1; i < n; i++) {
        if (s[i] == s[curPos]) curLen++;
        else {
            if (curLen > maxLen) { maxLen = curLen; maxPos = curPos; }
            curLen = 1; curPos = i;
        }
    }
    if (curLen > maxLen) { maxLen = curLen; maxPos = curPos; }
    
    char *res = (char*)malloc(maxLen + 1);
    strncpy(res, s + maxPos, maxLen);
    res[maxLen] = '\0';
    return res;
}

三、最長公共子串 (LCS) - DP O(n²)


void findMaxSubstr(const char *s1, const char *s2, char *res) {
    int n = strlen(s1), m = strlen(s2);
    int maxLen = 0, maxPos = -1;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            int k = 0;
            while (i+k < n && j+k < m && s1[i+k] == s2[j+k]) k++;
            if (k > maxLen) { maxLen = k; maxPos = i; }
        }
    
    if (maxPos == -1) res[0] = '\0';
    else { strncpy(res, s1 + maxPos, maxLen); res[maxLen] = '\0'; }
}

進階：後綴自動機/陣列可達 O(n+m)，KMP 變體 Extend-KMP 亦可線性求解。

四、字串查找與計數 (strstr 實現)


// 基礎版：返回首次出現位置
char* my_strstr(const char *haystack, const char *needle) {
    if (!*needle) return (char*)haystack;
    for (; *haystack; haystack++) {
        const char *h = haystack, *n = needle;
        while (*h && *n && *h == *n) { h++; n++; }
        if (!*n) return (char*)haystack;
    }
    return NULL;
}

// 計數版
int count_substr(const char *s, const char *sub) {
    int count = 0;
    while ((s = my_strstr(s, sub))) { count++; s++; }
    return count;
}

KMP：預處理 next 陣列，查找 O(n+m)，適合多次查找同模式。

五、去除重複字元 (保留首次出現)


void removeDuplicates(char *s) {
    bool seen[256] = {false};
    int write = 0;
    for (int read = 0; s[read]; read++) {
        unsigned char c = s[read];
        if (!seen[c]) {
            seen[c] = true;
            s[write++] = c;
        }
    }
    s[write] = '\0';
}

六、字串全排列 (字典序)


void permute(char *s, int l, int r) {
    if (l == r) { puts(s); return; }
    for (int i = l; i <= r; i++) {
        swap(s[l], s[i]);
        permute(s, l+1, r);
        swap(s[l], s[i]);  // 回溯
    }
}

// 字典序生成 (std::next_permutation 邏輯)
bool next_permutation(char *s, int n) {
    int i = n - 2;
    while (i >= 0 && s[i] >= s[i+1]) i--;
    if (i < 0) return false;
    int j = n - 1;
    while (s[j] <= s[i]) j--;
    swap(s[i], s[j]);
    reverse(s + i + 1, s + n);
    return true;
}

七、字串反轉


void reverse(char *s, int len) {
    for (int i = 0; i < len/2; i++)
        swap(s[i], s[len-i-1]);
}

八、第一個不重複字元


char firstUniqueChar(const char *s) {
    int count[256] = {0};
    for (int i = 0; s[i]; i++) count[(unsigned char)s[i]]++;
    for (int i = 0; s[i]; i++) 
        if (count[(unsigned char)s[i]] == 1) return s[i];
    return '\0';
}

九、去除相鄰重複字元


// 棧模擬：O(n) 時間 O(n) 空間
void removeAdjacentDuplicates(char *s) {
    int top = -1;
    for (int i = 0; s[i]; i++) {
        if (top >= 0 && s[top] == s[i]) top--;
        else s[++top] = s[i];
    }
    s[top+1] = '\0';
}

十、判斷是否含回文子串


bool hasPalindromeSubstr(const char *s, int minLen) {
    int n = strlen(s);
    for (int center = 0; center < 2*n-1; center++) {
        int l = center / 2;
        int r = l + center % 2;
        while (l >= 0 && r < n && s[l] == s[r]) {
            if (r - l + 1 >= minLen) return true;
            l--; r++;
        }
    }
    return false;
}

十一、最長回文子串

DP 解法 O(n²)


string longestPalindromeDP(const string &s) {
    int n = s.size();
    vector> dp(n, vector(n));
    int maxLen = 1, start = 0;
    
    for (int i = 0; i < n; i++) dp[i][i] = true;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i+len <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = (s[i] == s[j]) && (len == 2 || dp[i+1][j-1]);
            if (dp[i][j] && len > maxLen) { maxLen = len; start = i; }
        }
    }
    return s.substr(start, maxLen);
}

中心擴展法 O(n²) 空間 O(1)


string longestPalindromeCenter(const string &s) {
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
        return make_pair(l+1, r-1);
    };
    
    int bestL = 0, bestR = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        auto [l1, r1] = expand(i, i);
        auto [l2, r2] = expand(i, i+1);
        if (r1 - l1 > bestR - bestL) { bestL = l1; bestR = r1; }
        if (r2 - l2 > bestR - bestL) { bestL = l2; bestR = r2; }
    }
    return s.substr(bestL, bestR - bestL + 1);
}

Manacher 算法 O(n)

線性時間求最長回文，面試加分項，建議掌握核心思想：插入特殊字元統一奇偶長度，利用對稱性避免重複擴展。

十二、字串循環移位包含判斷


bool isRotationSubstr(const char *s1, const char *s2) {
    int n = strlen(s1), m = strlen(s2);
    if (m > n) return false;
    char *double_s1 = (char*)malloc(2*n + 1);
    strcpy(double_s1, s1);
    strcat(double_s1, s1);
    bool res = strstr(double_s1, s2) != NULL;
    free(double_s1);
    return res;
}

十三、strcpy/strlen 實現與重疊處理


// strcpy 標準實現 (無重疊保護)
char* my_strcpy(char *dest, const char *src) {
    char *ret = dest;
    while ((*dest++ = *src++) != '\0');
    return ret;
}

// memmove 風格處理重疊
void* my_memmove(void *dest, const void *src, size_t n) {
    char *d = (char*)dest;
    const char *s = (const char*)src;
    if (d < s) while (n--) *d++ = *s++;
    else { d += n; s += n; while (n--) *--d = *--s; }
    return dest;
}

十四、中文字串去除英文字元


// 簡易版：ASCII 字元 (高位為 0) 視為英文
void removeAscii(char *s) {
    int w = 0;
    for (int r = 0; s[r]; r++) {
        if ((unsigned char)s[r] >= 0x80)  // 非 ASCII
            s[w++] = s[r];
    }
    s[w] = '\0';
}
// 完整版需處理 UTF-8 多位元組邏輯

十五、連續出現最多子串 (Run-Length Encoding 相關)


void maxConsecutiveSubstr(const char *s, char *res, int *maxCount) {
    int n = strlen(s), curCount = 1, maxC = 1, maxPos = 0;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i-1]) curCount++;
        else { if (curCount > maxC) { maxC = curCount; maxPos = i-curCount; } curCount = 1; }
    }
    if (curCount > maxC) { maxC = curCount; maxPos = n-curCount; }
    strncpy(res, s + maxPos, maxC);
    res[maxC] = '\0';
    *maxCount = maxC;
}

複雜度總覽表

問題	朴素	優化	核心技巧
字串轉數值	O(n)	O(n)	溢位檢測、空白符號處理
最長相同字元子串	O(n)	O(n)	單次掃描
最長公共子串	O(n²m)	O(n+m)	後綴自動機/Extend-KMP
字串查找	O(nm)	O(n+m)	KMP/BM/Sunday
去重/首現	O(n²)	O(n)	位圖/哈希集合
全排列	O(n!)	O(n!)	回溯/字典序生成
最長回文	O(n³)	O(n)	Manacher/中心擴展
循環移位包含	O(n²)	O(n)	KMP搜尋 s1+s1