本文介绍字符串及其相关重要算法。

1 串的逻辑结构

字符串（String，简称串)：由零个或多个字符（Character）组成的有限序列，实际相当于元素为特定类型（字符型）的线性表。串中字符的个数n称为串长，串长n=0的串称为空串（用\empty表示）

相关重要概念：

• ⼦串（Substring）：主串中任意多个连续的字符组成的⼦序列，在主串中的位置以⼦串的第⼀个字符在主串中的位置来表示。
• 真子串：不包含主串自身但可以为空的子串

注：由⼀个或多个空格（特殊字符　）组成的串称为空格串

ADT String {
    数据对象: char a_i
    数据关系: (a_{i-1}, a_i)
    基本操作：
        strAssign(&Str, ch) // 赋值操作，将串Str赋值为字符数组ch
        strCpy(&Str1, Str2) // 复制操作，根据串Str2复制给Str1
        isEmpty(Str)    // 判空操作
        strLen(Str) // 求串⻓，返回串Str的元素个数
        strCmp(Str1, Str2)  // ⽐较操作，先⽐较字典序，若⽐较结束则再⽐串⻓，⻓者⼤
        subStr(&Sub, Str, pos, len) // 求⼦串，⽤Sub返回主串Str中第pos个字符起⻓度为len的⼦串
        strCat(&Str, Str1, Str2)    // 串连接，Str = Str1 + Str2
        index(Str, Sub) // 定位操作，判定主串中是否存在与串Sub相等的⼦串
        clearStr(&Str)  // 清空操作
        destroyStr(&S)  // 销毁操作
} ADT String

---

2 串的存储结构

顺序存储：分为以下两种，常为⾼级程序设计语⾔所采⽤

1. 定⻓存储结构：相当于线性表中顺序表的静态分配存储，C语言中在表示字符串的字符数组结尾通常有⼀个结束标记字符'\0'。使用scanf()读取字符串时，超过预定义串⻓MAXSIZE的串值会被舍去，称为截断。

# define MAXSIZE 1010
typedef struct String {
    char str[MAXSIZE + 1];  // 多定义一个空间，留给结束标记'\0'
    int length;
} String;

2. 变⻓存储结构：相当于线性表中顺序表的动态分配存储，⼜称堆分配存储表示<，最为常用。C语言中使用malloc()和free()函数在自由存储区（堆）中动态管理串的存储，仍以连续地址存储。

typedef struct String {
    char *ch;
    int length;
} String;

块链存储结构：相当于线性表的链式存储结构，即链表。每个结点称为块，可设定最多存储⼀个或多个字符；整个链表称为块链结构。最后⼀个结点存储不满时通常⽤'#'补上。

---

3 串的基本操作

实际运用中常通过<cstring>库中提供的各种函数（strlen()、strcmp()、strcpy()等）来处理以字符数组实现的字符串，若使用C++则还可直接用std::string类（预置大量实用成员函数）、各种流（stringstream等）以及算法库<algorithm>中的各种辅助函数（reverse()等）。本节以上一节中定义的变⻓存储结构为例，使用C/C++伪代码详细介绍串的各种操作的底层代码实现：

1. 赋值操作：将字符数组赋值给字符串类

bool strAssign(String &str, char *ch) {
    if (str.ch) free(str.ch);   // 若str非空则先清空

    int len = 0;
    char *c = ch;   // c指向ch所指的连续存储单元的首地址
    while (*c) {
        len++;
        c++;
    }

    if (len == 0) { // 空串
        str.ch = NULL;
        str.length = 0;
    } else {    // 非空串
        str.ch = (char*) malloc((len + 1) * sizeof char);
        if (!str.ch) return false;  // 若分配失败则表示赋值失败
        c = ch;
        for (int i = 0; i <= len; i++, c++) {   // 要将'\0'也复制过来，故为“<=”
            str.ch[i] = *c;
        }
        str.length = len;
    }
    return true;
}

2. 取串长度：与<cstring>库中的strlen()不同，无需从头到尾遍历一遍，直接返回成员变量即可（此处演示仅表明串长不包括字符数组末尾的'\0'）

int strLength(String str) {
    return str.length;
}

3. 串比较：设两串s1与s2中的待比较字符分别为c1和c2，则
   • 若c1的ASCII码小于c2的ASCII码，则返回s1小于s2的标记（一个负数）
   • 若c1的ASCII码大于c2的ASCII码，则返回s1大于s2的标记（一个正数）
   • 若c1的ASCII码等于c2的ASCII码，则按照之前的规则继续比较两串中的下一对字符
   • 若反复进行上述步骤仍未比较出s1与s2大小，则先结束的串为较小串；两串同时结束则返回两串相等的标记（0）

int strCompare(String s1, String s2) {
    for (int i = 0; i < s1.length && i < s2.length; i++) {
        if (s1.ch[i] != s2.ch[i]) return s1.ch[i] - s2.ch[i];
    }
    return s1.length - s2.length;
}

4. 串连接：将str2接在str1之后，赋给str

bool concatenate(String &str, String str1, String str2) {
    if (str.ch) free(str.ch);

    str.ch = (char*) malloc((str1.length + str2.length + 1) * sizeof char);
    if (!str.ch) return false;

    int i = 0;
    while (i < str1.length) {   // 复制str1
        str.ch[i] = str1.ch[i];
        i++;
    }
    int j = 0;
    while (j <= str2.length) {  // 复制str2（应包括'\0'，故为“<=”）
        str.ch[i + j] = str2.ch[j];
        j++
    }
    str.length = str1.length + str2.length;
    return true;
}

5. 求子串：从str中取一个以pos为起点、长度为len的子串substr

bool substring(String &substr, String str, int pos, int len) {
    if (pos < 0 || pos >= str.length || len < 0 || len > str.length - pos) return 0;

    if (substr.ch) free(substr.ch);

    if (len == 0) { // 取长为0（空串）
        substr.ch = NULL;
        substr.length = 0;
    } else {
        substr.ch = (char*) malloc((len + 1) * sizeof char);
        int i = pos, j = 0; // 主串str下标i ∈ [pos, len)，子串substr下标j从0开始
        while (i < pos + len) {
            substr.ch[j] = str.ch[i];
            i++;
            j++;
        }
        substr.ch[j] = '\0';    // 结尾赋'\0'
        substr.length = len;
    }
    return true;
}

6. 清空串

void clearString(String &str) {
    if (str.ch) {
        free(str.ch);
        str.ch = NULL;  // 完全清空串
    }
    str.length = 0;
}

---

4 模式匹配

在模式匹配算法中，所有串的字符数组均从下标1开始存储，注意与上⼀节区分。可通过如下方式从下标1开始读取主串和模式串：

scanf("%s%s", S.ch + 1, P.ch + 1)

4.1 暴⼒匹配算法

暴⼒匹配算法（Brute Force，BF）：使⽤双指针逐⼀⽐较主串与模式串，同时记录主串上⼀次匹配的起始位置，发⽣不匹配则回溯。

性能：T(m,n)=O(m \cdot n)，其中m,n分别为主串与子串的长度

/* 主串S与模式串P的暴⼒模式匹配 */
int index(String S, String P) {
    int i = 1, j = 1, pos = i;  // i、j分别作为主串和模式串的索引，pos记录⽐较的开始位置
    while (i <= S.length && j <= P.length) {
        if (S.ch[i] == P.ch[j]) {   // 遍历字符相同，则同时后移
            i++;
            j++;
        } else {    // 不同则主串索引i回溯，模式串索引j重置为1，更新pos
            i = pos + 1;
            j = 1;
            pos = i;
        }
    }
    if (j > P.length) return pos;   // 模式串遍历结束，模式匹配成功，返回模式串所在位置
    return 0;   // 模式匹配失败，返回0
}

4.2 KMP算法

KMP算法（The Knuth-Morris-Pratt Algorithm）用于快速从主串中找到与模式串相同的串，历经几十年发展，存在多种版本。

• 性能：T(m,n)=O(m+n)
• 提⾼模式匹配效率的关键：主串位置i⽆需回退，即尽可能利⽤匹配失败的信息，尽量减少主串与模式串的匹配次数。

手工模式匹配步骤：

1. 顺次匹配主串与模式串，当出现不匹配时往前找主串与模式串不匹配点之前真子串的最⼤公共前后缀
2. 将模式串的串头从最⼤前缀处平移⾄最⼤后缀处，继续第1步操作
   • 特别地，当公共前后缀为空时（缀⻓为0），串头直接移⾄不匹配点处
3. 当模式串遍历结束则表示匹配成功，否则匹配失败

求解next数组简易方法：对着模式串P操作

1. 令\text{next}[1]=0，易得\text{next}[2]=1
2. 当j>1时，\text{next}[j]=P[j]的最大公共前后缀长度+1
   

   虽然极为罕见，但早年统考题亦有过令串从下标0开始存储，此时应取\text{next}[0]=-1，则当j>1时\text{next}[j]直接为最大公共前后缀长度

原版代码实现（求next数组的过程形式上近似于模式串对模式串进行模式匹配）：

/* 获取next数组 */
void getNext(String P, int next[]) {
    int i = 1, j = 0;   // i为主串后缀结束位置，j为模式串前缀结束位置（初值0）
    next[1] = 0;    // 预设为0
    while (i < P.length) {
        if (j == 0 || P.ch[i] == P.ch[j]) { // 遍历字符相同或j回溯到头，则更新next数组
            i++;
            j++;
            next[i] = j;
        } else {    // 遍历字符不同，则j回溯
            j = next[j];
        }
    }
}

/* KMP算法 */
int kmp(String S, String P, int next[]) {
    int i = 1, j = 1;   // i、j分别为主串和模式串的索引
    while (i <= S.length && j <= P.length) {
        if (j == 0 || S.ch[i] == P.ch[j]) { // 遍历字符相同或j回溯到头，则同时后移
            i++;
            j++;
        } else {    // 遍历字符不同，则j回溯
            j = next[j];
        }
    }
    if (j > P.length) return i - P.length;  // 模式串遍历结束，模式匹配成功，返回模式串所在位置
    return 0;   // 模式匹配失败，返回0
}

求解nextval数组简易方法：对着求得的next数组与模式串P操作

1. 令\text{nextval}[1]=0，易得\text{nextval}[2]=1
2. 当j>1时，比较当前位置字符P[j]与其next值所指示的字符P[\text{next}[j]]
   • 若两者相同，则直接与之相同，即\text{nextval}[j]=\text{nextval}[\text{next}[j]]
   • 若两者不同，则沿用自己的next值，即\text{nextval}[j]=\text{next}[j]
     

     口诀：相同则相同，不同则不同（沿用自己）！

改进版代码实现（用nextval数组替换next数组）：

/* 获取nextval数组 */
void getNextval(String P, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0; // 同样预设为0
    while (i < P.length) {
        if (j == 0 || P.ch[i] == P.ch[j]) {
            i++;
            j++;
            if (P.ch[i] != P.ch[j]) nextval[i] = j + 1; // 不同则不同
            else nextval[i] = nextval[j];   // 相同则相同
        } else {
            j = nextval[j];
        }
    }
}

/* 改进版KMP算法 */
int kmp2(String S, String P, int nextval[]) {
    int i = 1, j = 1;
    while (i <= S.length && j <= P.length) {
        if (j == 0 || S.ch[i] == P.ch[j]) {
            i++;
            j++;
        } else {
            j = nextval[j]; // 使用nextval数组
        }
    }
    if (j > P.length) return i - P.length;
    return 0;
}

【例】模式串ababcabc的next数组与nextval数组（串下标从1开始）：

下标	1	2	3	4	5	6	7	8
P[j]	a	b	a	b	c	a	b	c
\text{next}[j]	0	1	1	2	3	1	2	3
\text{nextval}[j]	0	1	0	1	3	0	1	3

---

A 双指针思想*

常见的双指针问题可大致分为以下两类：

1. 对于一个序列，用两个指针维护一段区间
2. 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

朴素双指针O(n^2)：

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // ...
    }
}

优化双指针O(n)：

/* i为子序列右端点，j为左端动点 */
for (int i = 0, j = 0; i < n; i++) {
    while (j < i && check(i, j)) {
        // ...
        j++;
    }
    // ...
}

/* i为子序列左端点，j为动态右端动点 */
for (int i = 0; i < n;) {
    int j = i;
    while (j < n && check(i, j)) {
        // ...
        j++;
    }
    // ...
    i = j + 1;  // 将i直接移至j附近
}

---

B 模拟处理思路*

模拟题中字符串常见处理方式：

1. 截取字符串：利用s.substr()方法修缮串：

/* 截掉串头k个字符 */
s = s.substr(k);

/* 剔除下标为pos的字符 */
s = s.substr(0, pos) + s.substr(pos + 1);

/* 取倒数k个字符 */
string sf = s.substr(s.size() - k);

2. 类型转换：C++中将字符串转换成整数、实数类的函数原型如下所示，可利用这些函数来检测某数据是否属于数值类型，对非法输入会抛出错误，可用try-catch语句抓取，由此来判断是否。但这些函数返回值实为字符串前几位符合数值类型定义的部分（如stoi("6.969pog")会返回6.969而不会报错），故可创建一个下标变量idx（size_t类型）并将其地址作为第二参数传入函数，由于函数第二参数是指针型故会改变idx的值，之后比较idx与字符串长度大小来特判。

   // string to int（整数）参数：字符串，起始下标（指针型，默认为0/空），字符串表示的数的进制（默认为10进制）
   int stoi(const string &str, size_t *idx = 0, int base = 10);
   　　　
   // string to float（单精度浮点数）参数：字符串，起始下标（指针型，默认为0/空）
   float stof(const string &str, size_t *idx = 0);
   　　　
   // string to double（双精度浮点数）参数同stof
   double stod(const string &str, size_t *idx = 0);

   【例】用stof()判断输入字符是否为实数：

   string num;
   cin >> num;
   float x;
   bool flag = true;   // 标识初始化为是
   try {
       size_t idx = 0;
       x = stof(num, &idx);
       if (idx < (int)num.size()) flag = false;
   } catch (...) { // 接收错误（ERROR）,这里设置为任何错误
       flag = false;
   }

3. 找n个串的最大公共后缀：建立串数组s[N]——

   1. 以s[0]为标准串，从长到短取其长度为k的后缀（称为标准后缀）：

      // k为后缀长度，亦表示倒数k个字符
      string sf = s[0].substr(s[0].size() - k);

   2. 每轮的标准后缀依次与剩余n - 1个串比较，判断不匹配条件：

      // 标准后缀长度k大于某串或发生不匹配
      if (k > s[i].size() || s[i].substr(s[i].size() - k) != sf) ...

   3. 发生不匹配则立即结束此轮后缀比较，执行下一轮；跳出比较循环则表示找到最大公共后缀。

4. 数字串拼接最小数：求一组数字串能拼接成的最小数，使用std::sort()时可定义如下排序函数排列串：

   bool cmp(string a, string b) {
       return a + b < b + a;
   }

5. 格式化输入输出：使用函数sscanf(...)可格式化读入字符串中的有用数据（配合上一条即可按字符串特征编写相对应的算法读入所需数据）。与之对应的函数sprintf(...)可格式化赋回字符串，效果类似直接相加。

   • 两种结果输出方式：
     1. 现场输出（无重度修改需求）
     2. 用std::string串res存储结果，最终修缮后统一输出（对格式要求高，如对行末空格的处理）
   • 对于需要将字符按特定图形输出的，除了即时输出外，还可选择开一个矩阵，将字符填入，最后遍历矩阵输出（尽量分治）。

6. 时空差的计算：常用的时空差计算方式如下

   1. 定基准：以某点\{0\}为原点，统一单位，将\{b\}\ - \{a\}转化为(\{b\} - \{0\}) - (\{a\} - \{0\})
   2. 以空间换时间：推广前缀和算法的思想，提前算出定义域上各时间点i上的值（\{i\} - \{0\}），可用递推将结果存入容器中。
      • 【例】求某秒在当天对应时刻距离原点累积收费：

        for (int i = 1; i < MAXD; ++i) sum[i] = sum[i - 1] + cost[(i - 1) % 1440 / 60];
        // 注：
        //  1（i - 1）：题中规定收费区间左闭右开
        //  2（取余于1440）：定位至一天内
        //  3（除以60）：换算成小时（会自动取整）

   3. 提前剪枝：如银行多窗口排队问题，窗口结束服务时刻早于下一个来访者（期间保持空闲），则可直接将结束服务时刻挪至来访者到来时刻，便于后续计算（省去判别异常情况）。

7. 对象存储：

   • 可用map或unordered_map高效存储对象数据，将对象与其结构体一一对应，或者押入vector或堆中。
   • 自定义结构体排序——重载不等号：数组重载小于号<，优先队列重载大于号>（同std::sort()中cmp函数。记忆：数组左观，优先队列右观）。语法示例如下（以小于号为例，将学生结构体按人名字典序比较）——

     bool operator<(const Student& t) const { return name < t.name; }

---

C 动态规划入门*

入档时间：2023年

动态规划（Dynamic Programming，DP）为PAT顶级考试大纲明确要求考点，在当前甲级大纲中已不再出现，但早年真题出现过相关内容（5次），故尽管出题可能性较小，本文仍放出常用的DP分析方法，对处理某些复杂题目应有所帮助。若单纯想在短期内通过甲级考试，可暂且略过该部分，但最好了解一下思想尤其是树形DP的方法。

C.1 一般DP*

难度略高，仅供参考。

状态表示：一般用n维数组f存储所有方案

• 集合f(X)：逻辑上象征着前提条件为X时各种方案的集合，作为变量时存储前提条件为X时最优方案的属性。一个n维问题在条件X下各种方案的集合记为f(i_1,i_2,\cdots ,i_n)，其中i_1,i_2,...,i_n为各种制约因素。
• 属性：问题的核心，所有方案围绕它展开，由f(X)存储。

状态计算：集合f(X)应可以划分为具有相似特征的若干互不相交的子集合，且子集合中都包含相同的边界元素（记为c，其已知权值记为W_c），则该集合的最优方案（即f(X)的值）取决于剔除该共有元素后各子集合中的最优方案。由此得出如下关系式：

\begin{aligned}
f(X)=\text{best}\{f(X- \{c\}) + W_c,\ W_c\}
\end{aligned}

化简后即得如下递推式（其中f(\empty)表示已知的底线方案，所有劣于最低要求\empty的方案皆会被转化成它）：

\begin{aligned}
f(X)=\text{best}\{f(X- \{c\}),\ f(\empty)\}+W_c
\end{aligned}

在利用上述递推式计算f(X)的基础上，绝大多数复杂情形还要求进行其他操作，如维护一个区间等，可在判断底线方案或更新结果时执行。方法灵活多变，不同情形实现方式各有差异，归根到底均为围绕上述递推更新方案思想的变式，可通过大量做题多总结来积累经验。

C.2 树形DP*

在树的DFS算法基础上可得出树形DP。相较于上述的DP通法，该算法的构建与书写都极为容易。通过引入双亲指针这一概念（另见“树与⼆叉树编程练习”之“其他⼆叉树存储形式”例3），建模时不再需要用到邻接表存储树形结构数据，只需开一个存储结点的双亲的一维数组p[] （另见双亲表示法）即可。以下以求根结点到指定结点的距离为例来浅析树形DP的思路。

参照一般DP法，令f[i]为结点i到根结点root的距离，函数DFS(u)返回根结点到结点u的距离（在树形DP中常称为记忆化搜索），则该函数可由如下伪代码简易表示：

int DFS(u) {
    if (/* f(u) 已存在 */) return f[u];
    if (/* u 是 root */) return f[u] = 0;    // 等价于 f[u] = 0; return f[u];
    return f[u] = DFS(p[u]) + 1;    // 等价于 f[u] = DFS(p[u]) + 1; return f[u];
}

可知该算法的时间复杂度T(n)=O(n)依旧是线性级的，毫不逊于常规的建树+DFS方法，但显然在解题速度与思维高度上更胜一筹。