字符串总结|dc的house

字符串是编程中非常常见的数据类型，几乎所有的编程语言都提供了对字符串的支持。在C/C++中，字符串的处理方式与其他语言有所不同，尤其是在底层实现上。本文将从字符串的基础定义、库函数的使用原则、双指针法、反转系列问题以及KMP算法等方面，全面总结字符串的相关知识，并结合代码示例帮助大家更好地理解和掌握字符串的处理技巧。

1. 什么是字符串？

字符串是由若干字符组成的有限序列，可以理解为一个字符数组。在C/C++中，字符串的实现方式有所不同。

1.1 C语言中的字符串

在C语言中，字符串是以字符数组的形式存储的，并且以'\0'作为字符串的结束标志。例如：

char a[5] = "asd";
for (int i = 0; a[i] != '\0'; i++) {
    // 遍历字符串
}

在这个例子中，a是一个字符数组，存储了字符串"asd"，并在末尾自动添加了'\0'作为结束符。

1.2 C++中的字符串

C++提供了string类，它是一个封装了字符数组的类，提供了丰富的字符串操作接口。与C语言不同，string类不需要以'\0'作为结束标志，而是通过size()方法获取字符串的长度。例如：

string a = "asd";
for (int i = 0; i < a.size(); i++) {
    // 遍历字符串
}

1.3 `vector<char>` 和 `string` 的区别

vector<char>和string在基本操作上没有太大区别，但string提供了更多的字符串处理接口。例如，string重载了+运算符，可以直接用于字符串拼接，而vector<char>则没有这样的功能。因此，处理字符串时，通常推荐使用string类型。

2. 要不要使用库函数？

在初学阶段，很多人会依赖库函数来完成字符串操作，例如substr、split、reverse等。然而，过度依赖库函数可能会导致对底层实现的不了解，从而在面试或实际开发中遇到困难。

2.1 库函数的优缺点

优点：库函数通常经过优化，使用方便，能够快速解决问题。
缺点：如果对库函数的实现原理不了解，可能会导致代码效率低下或无法应对复杂场景。

2.2 使用库函数的原则

关键部分避免使用库函数：如果题目关键部分可以直接用库函数解决，建议不要使用库函数，而是自己实现。
了解库函数的实现原理：如果库函数只是解题过程中的一小部分，并且你已经清楚其内部实现原理，可以考虑使用库函数。

例如，在反转字符串时，可以使用reverse库函数，但更好的方式是手动实现反转逻辑，以加深对双指针法的理解。

3. 双指针法

双指针法是字符串处理中非常常用的技巧，尤其是在数组、链表和字符串中。以下是双指针法的几个典型应用场景。

3.1 反转字符串

在反转字符串时，可以使用双指针法，一个指针指向字符串的开头，另一个指针指向字符串的末尾，然后交换两个指针指向的字符，直到两个指针相遇。

void reverseString(string& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        swap(s[left], s[right]);
        left++;
        right--;
    }
}

3.2 替换空格

在替换空格的问题中，双指针法同样适用。例如，将字符串中的空格替换为%20：

string replaceSpaces(string s) {
    int count = 0;
    for (char c : s) {
        if (c == ' ') count++;
    }
    int oldSize = s.size();
    s.resize(s.size() + count * 2);
    int newSize = s.size();
    for (int i = oldSize - 1, j = newSize - 1; i >= 0; i--, j--) {
        if (s[i] != ' ') {
            s[j] = s[i];
        } else {
            s[j] = '0';
            s[j - 1] = '2';
            s[j - 2] = '%';
            j -= 2;
        }
    }
    return s;
}

3.3 移除元素

在移除元素的问题中，双指针法可以高效地完成操作。例如，移除数组中等于某个值的元素：

int removeElement(vector<int>& nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.size(); fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

4. 反转系列问题

反转系列问题是字符串处理中的经典问题，通常考察对代码的掌控能力。

4.1 反转字符串II

在反转字符串II的问题中，要求每隔2k个字符反转前k个字符。可以通过在for循环中调整步长来实现：

string reverseStr(string s, int k) {
    for (int i = 0; i < s.size(); i += 2 * k) {
        if (i + k <= s.size()) {
            reverse(s.begin() + i, s.begin() + i + k);
        } else {
            reverse(s.begin() + i, s.end());
        }
    }
    return s;
}

4.2 反转字符串中的单词

在反转字符串中的单词问题中，要求反转字符串中的每个单词，同时去除多余的空格。可以通过先整体反转再局部反转的方式实现：

string reverseWords(string s) {
    // 去除多余空格
    int slow = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != ' ') {
            if (slow != 0) s[slow++] = ' ';
            while (i < s.size() && s[i] != ' ') {
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow);
    // 整体反转
    reverse(s.begin(), s.end());
    // 局部反转
    int start = 0;
    for (int i = 0; i <= s.size(); i++) {
        if (i == s.size() || s[i] == ' ') {
            reverse(s.begin() + start, s.begin() + i);
            start = i + 1;
        }
    }
    return s;
}

5. KMP算法

KMP算法是字符串匹配中最重要的算法之一，其核心思想是通过前缀表避免不必要的匹配。

5.1 前缀表

前缀表记录了字符串中每个位置之前（包括当前位置）的子串的最长相等前后缀的长度。例如，字符串"aabaaf"的前缀表为[0, 1, 0, 1, 2, 0]。

5.2 KMP算法的实现

KMP算法的实现分为两步：

构建前缀表。
使用前缀表进行匹配。

以下是KMP算法的完整实现：

void getNext(int* next, const string& s) {
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < s.size(); i++) {
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j;
    }
}

int strStr(string haystack, string needle) {
    if (needle.size() == 0) return 0;
    int next[needle.size()];
    getNext(next, needle);
    int j = 0;
    for (int i = 0; i < haystack.size(); i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == needle.size()) {
            return i - needle.size() + 1;
        }
    }
    return -1;
}