PTA上如果留意一下，会发现《串的算法设计》这类题被很多同学称作“看起来送分、交上去送命”。尤其是顺序串上的删除算法，一个函数写下来不过十几行，但常驻的最大测试点能卡掉一大半提交。问题从来不是你不会写循环，而是你没有在动手之前想清楚：顺序串到底是个什么东西，删除操作的底层动作是什么，边界条件该怎么设。

我见过太多抱着链表思维去写顺序串的人：脑子里想着“删掉一个结点，把指针绕过去就行”，结果到了字符数组里，删掉一个字符意味着后面所有字符都要往前挪一位。这就是顺序存储和链式存储最本质的区别。这篇文章不绕弯子，直接从顺序串的存储模型讲起，把按位置删除、按区间删除、删除所有指定字符、删除所有子串这四类需求逐一拆开，最后落到PTA判题环境的测试点规律上。不管你是正在学数据结构的本科在读，还是在刷题备考408、为天梯赛做准备，只要在顺序串上栽过跟头，这篇应该能帮你一次理顺。

1. 顺序串的存储模型：删除操作为什么“牵一发而动全身”

1.1 定长顺序串和变长顺序串，PTA题里到底默认哪种

顺序串，说白了就是用一段连续的存储空间来存字符串。PTA的题目里最常见的结构体定义是严蔚敏《数据结构》教材风格的：

#define MAXLEN 255 typedef struct { char ch[MAXLEN + 1]; // 下标0闲置，串值从下标1开始存放 int length; // 当前串长 } SString;

也有不少题目直接用下标0开始的定长数组：

typedef struct { char ch[MAXLEN]; // 下标0开始存放 int length; } SString;

这两种定义在删除算法上只有一处不同——循环的起点和边界写法，后面我会把两个版本都写出来。关键是要分清“定长”和“变长”。定长顺序串的意思是，MAXLEN一旦定了，串的长度不能再超过它，插入和赋值时超出部分要么截断要么丢弃。而变长顺序串用动态数组实现，可以扩容，但PTA的基础算法题大多数不需要你去搞动态扩容，那是高阶内容。

你还要注意一个细节：很多教材为了让下标和位序一致，故意让ch[0]不存字符，这样“第pos个字符”就是ch[pos]，不用做pos-1的换算。这个习惯在串的算法设计题里很常见，所以下面讲算法流程时，我默认走“下标1版本”，如果你刷的题是下标0版本，换算关系我在对应章节会单独标注。

1.2 删除的本质是“重叠搬移”，不是“逻辑擦除”

顺序串的删除操作，表面上是“去掉一段字符”，底层动作是“把后面的字符整体往前搬”。打个比方：链表删除像在火车车厢里摘钩子，把一节车厢解下来，前后车厢重新连接；顺序串删除像从停满车的停车场开走一辆车，后面所有车都必须往前倒一把，腾出空位。

这个搬移过程必须满足一个要求：源区间和目标区间是重叠的，但方向必须从前向后搬。假设你要删除从pos开始、长度为len的一段，存活下来的后半段字符原来的下标是从pos+len到length，它们要搬到的目标下标是从pos到length-len。循环一定是：

for i = pos + len to length do ch[i - len] = ch[i]

有的同学图省事，先把要留下的部分拷到一个新数组，再拷回去。这样写在小规模数据上没问题，但浪费了一倍空间，而且PTA的检查函数可能会对比ch数组里别的位置是否残留了脏数据——拷来拷去很容易留尾巴。顺序串删除的关键就是“原地搬移”，加一个length的更新就够了。

这个模型想清楚之后，剩下的所有删除算法都是在这条循环上做文章。

2. 按位置删除：一个字符和一段连续区间的完整流程

2.1 删除单个字符：三个边界条件少一个都错

先写最简单的情况——删除第pos个字符。完整函数如下（下标1版本）：

int StrDeleteChar(SString *S, int pos) { if (S == NULL) return 0; // 指针本身是空，直接拒绝 if (pos < 1 || pos > S->length) return 0; // 位置非法 for (int i = pos + 1; i <= S->length; i++) { S->ch[i - 1] = S->ch[i]; } S->length--; return 1; }

返回1表示删除成功，返回0表示失败。为什么非要返回值？因为PTA函数题里，判题器经常要求你返回Boolean或用0/1标记操作是否成功，自己写main的时候你是大爷，但写给Judge看的时候，返回值就是你和判题系统之间的协议。

这个函数里真正的难点只有一个：pos的合法范围。很多新手写的是pos < 0，忘了下标1版本里第一个字符的位置是1，不是0；还有人漏掉pos > S->length，结果循环越界访问ch数组，轻则答案错误，重则运行段错误。

如果你用的是下标0版本，边界就改成：

if (pos < 0 || pos >= S->length) return 0; for (int i = pos + 1; i < S->length; i++) { S->ch[i - 1] = S->ch[i]; } S->length--;

两个版本本质相同，只是“第1个字符”的坐标差了1。自己脑海里的坐标轴一定要和题目的结构体定义对齐，这是顺序串题里最容易被忽视的基础问题。

2.2 删除一段连续区间：先判断合法性再谈搬移

删除一段连续子串更常用，函数签名一般是StrDelete(S, pos, len)，表示删除从pos起长度为len的子串。C语言风格代码：

int StrDelete(SString *S, int pos, int len) { if (S == NULL) return 0; if (pos < 1 || pos > S->length) return 0; if (len < 0) return 0; if (len > S->length - pos + 1) return 0; // 要删的比剩下的还多 for (int i = pos + len; i <= S->length; i++) { S->ch[i - len] = S->ch[i]; } S->length -= len; return 1; }

最后那个条件len > S->length - pos + 1，其实是把“删除到尾”和“非法删除”区分开的唯一标准。举个例子，串是“ABCDEFG”，length=7，pos=5，len=4。此时S->length - pos + 1 = 7 - 5 + 1 = 3，len=4比3大，所以非法。如果len=3，那么删除的是“EFG”，执行完length变成4，串变成“ABCD”，这是合法的。

这个判断很多人会写成pos + len > S->length，也算对，但更容易暴露一个理解偏差：你其实是在检查“删除区间的右端点是否越过串尾”。写成len > S->length - pos + 1，直白反映了“能删的最大长度”这个物理意义。

我建议你手推一遍“ABCDEFG”删除pos=2、len=3的过程：被删的是“BCD”，i从5到7，ch[5]=E搬到ch[2]，ch[6]=F搬到ch[3]，ch[7]=G搬到ch[4]，最终ch数组是“AEFG...（后面残留原串的后续字符）”，length=4。注意！ch[5]、ch[6]里还残留着原来的F、G之类，但判题器只看前length个字符，所以length的更新是最后一道保险，漏了它，你输出的串会带着一堆垃圾尾巴。

3. 删除所有指定字符：快慢指针比“边查边删”靠谱多了

3.1 逐个删除为什么最坏会O(n²)

按位置删除的算法写熟之后，很多人遇到“删除串中所有等于字符x的字符”这道题，第一反应是遍历整个串，遇到等于x的就调一次StrDelete(S, i, 1)。逻辑上没问题，但如果你把复杂度算一下就知道大事不妙：

每删除一个字符，平均要搬移O(n)个元素；最坏情况下串里全是x，要删n个，总复杂度O(n²)。PTA的“最大测试点”通常给到长度几万的输入，O(n²)会稳稳卡进超时线。

举一个我亲眼见过的例子：串长度10000，全部是字符'a'，要求删除所有'a'。用“边查边删”的办法，每删除一个就调用StrDelete，第1次删除要搬9999个字符，第2次要搬9998个，累计搬移量接近5000万次。在C语言里可能勉强几秒内跑完，但加上判题服务器的进程调度，超时没商量。

3.2 快慢指针原地过滤的完整推演

正确做法是快慢指针，也叫原地过滤。慢指针slow指向“下一个可以放置保留字符的位置”，快指针fast从头到尾扫描每个字符，遇到不是x的就放进slow位置并让slow前进，遇到x就跳过。

void DeleteAllChar(SString *S, char x) { if (S == NULL || S->length == 0) return; int slow = 1; // 下标1版本，第一个保留字符要放到ch[1] for (int fast = 1; fast <= S->length; fast++) { if (S->ch[fast] != x) { S->ch[slow] = S->ch[fast]; slow++; } } S->length = slow - 1; }

这个算法一次遍历完成，时间复杂度O(n)，空间复杂度O(1)。它不需要单独的删除循环，因为它本质上是在“用保留字符覆盖被删字符的位置”。

我建议你把“abacada”删除'a'走一遍大脑模拟：fast扫到'b'，slow=1，ch[1]='b'，slow=2；fast扫到'a'，跳过；fast扫到'c'，ch[2]='c'，slow=3；fast扫到'a'，跳过；fast扫到'd'，ch[3]='d'，slow=4；fast扫到'a'，跳过。结束时fast=8、slow=5，length = 5-1 = 4，得到的串是“bcd”，正好是保留的那三个字符。

注意下标0版本要把slow和fast的初值都改成0，最后S->length = slow，别把版本弄混。很多人在这个“slow初值到底是0还是1”上栽跟头，其实根源还是没养成“先看结构体定义，再决定坐标”的习惯。

4. 删除所有子串：这里开始和模式匹配短兵相接

4.1 朴素匹配+删除+回退指针，什么时候不可用

删除单个字符只是热身，顺序串里更常见的题是“删除所有等于子串sub的内容”。比如“ababaabc”删除“aba”，期望结果是“bc”还是“abc”，取决于题目是删所有重叠出现还是非重叠出现。PTA题一般不会把话说死，你必须在看题的3秒内判断它要哪种。

非重叠删除的实现思路是：在主串中查找模式串，找到一个就调用StrDelete把它删掉，下一次查找的位置分两种情况。如果要求“删完继续找，允许新产生的重叠也被删掉”，查找起始位置必须回退到删除位置i，而不是i+sub.length。

int FindSub(SString S, SString T, int pos) { // 从S的pos位置开始查找子串T，找到返回位序，找不到返回0 int i = pos, j = 1; while (i <= S.length && j <= T.length) { if (S.ch[i] == T.ch[j]) { i++; j++; } else { i = i - j + 2; j = 1; } } if (j > T.length) return i - T.length; return 0; } void DeleteAllSub(SString *S, SString sub) { if (sub.length == 0) return; // 删除空子串是未定义行为，题目一般不会让删空 int pos = 1; while ((pos = FindSub(*S, sub, pos)) != 0) { StrDelete(S, pos, sub.length); // 关键：回退到pos，而不是pos + sub.length } }

为什么必须回退到pos？举一个最经典的例子：串“aaaaa”，子串“aa”。非重叠地删除会得到“a”，因为第一次删掉位置1到2的“aa”后，串变“aaa”，继续从位置3找，又会找位置3到4的“aa”，删掉后剩“a”。可如果需求是“删除后还要继续处理重叠导致的新的匹配”，就必须在新串里重新找。回退到pos后，循环会重新找位置1的“aa”，第二次删除位置1到2的“aa”，就剩下“aa”，第三次删除位置1到2，剩下空串。到底是“非重叠删除”还是“重复删除直到没有”，请一定以题目描述为准。

4.2 引入KMP后，“删完还要接着找”的next数组陷阱

如果主串和模式串都很长，朴素匹配的O(n*m)会超时，这时候想到KMP是自然的事。但KMP和删除操作结合时有一个坑：当你匹配到模式串并把它删除后，主串指针不能直接停在原地继续后移，因为你删除的这段内容可能和之前的内容拼出新的模式串。

比如主串“ABABA”，模式串“ABA”。第一次匹配到位置1到3，删除后剩“BA”。但如果主串是“AAAAA”、模式“AA”，KMP匹配到位置1到2后立即删除，主串指针停在3，继续扫描会漏掉位置2到3这个新形成的“AA”。

所以删除所有子串的正规优化思路是：不直接在主串上删，而是用一个输出数组cur充当“暂存栈”边扫描边处理。每读入一个主串字符，就把它压入cur，同时用KMP的next数组去匹配当前cur末尾与模式串的重叠部分；一旦发现cur末尾形成了完整的模式串，就把cur末尾模式串长度的内容弹出，这相当于做了一次“逻辑删除”。这个思路可以把总复杂度压到O(n+m)，思路彻底且不会漏匹配。

不过说实话，PTA的基础题用到这一步的少，大多数“删除所有子串”题用朴素匹配加StrDelete已经能过。KMP版本的实现适合你在备考中期自己写一遍，用来检验自己对next数组的理解是否真的扎实。

5. PTA判题视角下的边界测试点与可复用模板

5.1 PTA测试点的出题思路：免费午餐只有前两个

我在PTA上给学弟学妹答疑时间长了，发现判题系统的测试点在顺序串删除题上特别规律。我把它整理成一张表：

前两个测试点是“免费午餐”，只要函数主体写完基本能过。从第三个开始，考察的就是你删除前的参数校验写得完不完整。很多同学在“正常删除”用例上拿了满分，却栽在pos<1这种非法输入上，就是因为函数里少了第一道if。

5.2 一条可以复用的删除函数模板

最后给出一套我在刷题时反复用的模板，下标1版本，把单字符删除和区间删除统一封装：

// 删除S中从pos起长度为len的子串 int StrDelete(SString *S, int pos, int len) { if (S == NULL) return 0; if (pos < 1 || len < 0) return 0; if (pos > S->length || len > S->length - pos + 1) return 0; for (int i = pos + len; i <= S->length; i++) { S->ch[i - len] = S->ch[i]; } S->length -= len; return 1; } // 删除S中第pos个字符 int StrDeleteChar(SString *S, int pos) { return StrDelete(S, pos, 1); } // 删除S中所有等于x的字符，快慢指针实现 void DeleteAllChar(SString *S, char x) { if (S == NULL || S->length == 0) return; int slow = 1; for (int fast = 1; fast <= S->length; fast++) { if (S->ch[fast] != x) { S->ch[slow] = S->ch[fast]; slow++; } } S->length = slow - 1; }

这套模板的优点是分层清楚：底层是区间删除，单字符删除是它的特例，批量删除用快慢指针独立实现。在PTA函数题里，你需要根据题目给定的结构体和函数签名微调参数名，但核心逻辑不用大改。

提示：如果题目只要求返回删除是否成功，记得在所有非法参数分支都返回0；如果题目要求删除后输出字符串，length字段务必第一时间更新，否则后续基于length的输出会把残留字符一起带出来。

我在实际调试中还有一个习惯：写完函数先别急着提交，自己构造三个用例——删除第一个字符、删除最后一个字符、删除后整个串变空串。这三个用例过了，前三个测试点基本就稳了。等你在大数据测试点上碰了壁，再回来想想快慢指针为什么比“边查边删”快，应该就很有体感了。顺序串的删除算法说到底就是一次扎实的“重叠搬移”，把这个动作想透，后面学串的插入、合并、模式匹配都会顺畅很多。