字符串（String）

基本概念

字符串（String）是由零个或多个字符组成的有限序列，通常记为 s = a₁a₂…aₙ (0 ≤ n < ∞)。

名称：如 s 是变量名。
值：字符序列，常用双引号括起。
长度：字符个数 n。
空串：长度为 0 的字符串 ""。
子串：字符串中任意连续字符组成的序列，包括前缀（从首开始）和后缀（到末结束）。
主串：包含子串的字符串。

数据结构的三要素

逻辑结构

线性结构，字符之间呈线性关系，每个字符有唯一前驱和后继（除首尾外）。

存储结构

顺序存储
- 用一组地址连续的存储单元存放字符，如定长数组。
- 支持随机访问，时间复杂度 O(1)，空间利用率高。
链式存储
- 每个节点存放一个或多个字符，通过指针链接。
- 插入、删除灵活，但随机访问效率低（O(n)）。
各语言实现
- C：字符数组 + \0 结尾，string.h 提供操作。
- C++：string 类，封装动态数组。
- Java：String 类，不可变。
- Python：str 类型，不可变，支持切片等操作。

数据的运算

比较：按字符编码逐位比较，决定大小关系。
查找：单模式匹配（Brute Force, KMP, Boyer-Moore 等）和多模式匹配（Trie, AC 自动机等）。
连接、子串提取、替换、分割 等。

费曼理解

字符串就是一串字符排成的队列。你可以像数组一样访问某个位置的字符（如 s[0]），但许多语言中字符串不可变，修改会创建新对象。比较字符串就像查字典：先比第一个字母，相同再比第二个，直到分出大小；如果前缀相同，则短的更小。

内部实现

核心 API 手动实现示例（Python）

class MyString:
    def __init__(self, s=""):
        self._data = list(s)   # 用列表存储，实现可变效果（演示用）

    def length(self):
        return len(self._data)

    def char_at(self, index):
        return self._data[index]

    def compare(self, other):
        """返回 -1, 0, 1 表示小于、等于、大于"""
        i = 0
        while i < self.length() and i < other.length():
            if self._data[i] < other._data[i]:
                return -1
            elif self._data[i] > other._data[i]:
                return 1
            i += 1
        if self.length() < other.length():
            return -1
        elif self.length() > other.length():
            return 1
        return 0

    # 简单模式匹配（朴素算法）
    def index_of(self, pattern):
        n, m = self.length(), len(pattern)
        for i in range(n - m + 1):
            j = 0
            while j < m and self._data[i + j] == pattern[j]:
                j += 1
            if j == m:
                return i
        return -1

复杂度分析

操作	时间复杂度	空间复杂度	备注
字符访问	O(1)	O(1)	顺序存储
字符串比较（朴素）	O(min(n,m))	O(1)	逐字符
连接	O(n+m)	O(n+m)	新建字符串
子串提取	O(k)	O(k)	复制子串
模式匹配
Brute Force	O(n×m)	O(1)	最坏情况
KMP	O(n+m)	O(m)	利用失配信息
Boyer-Moore	平均 O(n/m)，最坏 O(n×m)	O(k)	字符集大小 k
Rabin Karp	平均 O(n+m)，最坏 O(n×m)	O(1)	滚动哈希
AC 自动机（多模式）	O(n + 总模式串长度)	O(总模式串长度)	构建 Trie + 失败指针