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的一段存活下来的后半段字符原来的下标是从poslen到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”length7pos5len4。此时S-length - pos 1 7 - 5 1 3len4比3大所以非法。如果len3那么删除的是“EFG”执行完length变成4串变成“ABCD”这是合法的。这个判断很多人会写成pos len S-length也算对但更容易暴露一个理解偏差你其实是在检查“删除区间的右端点是否越过串尾”。写成len S-length - pos 1直白反映了“能删的最大长度”这个物理意义。我建议你手推一遍“ABCDEFG”删除pos2、len3的过程被删的是“BCD”i从5到7ch[5]E搬到ch[2]ch[6]F搬到ch[3]ch[7]G搬到ch[4]最终ch数组是“AEFG...后面残留原串的后续字符”length4。注意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扫到bslow1ch[1]bslow2fast扫到a跳过fast扫到cch[2]cslow3fast扫到a跳过fast扫到dch[3]dslow4fast扫到a跳过。结束时fast8、slow5length 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而不是isub.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(nm)思路彻底且不会漏匹配。不过说实话PTA的基础题用到这一步的少大多数“删除所有子串”题用朴素匹配加StrDelete已经能过。KMP版本的实现适合你在备考中期自己写一遍用来检验自己对next数组的理解是否真的扎实。5. PTA判题视角下的边界测试点与可复用模板5.1 PTA测试点的出题思路免费午餐只有前两个我在PTA上给学弟学妹答疑时间长了发现判题系统的测试点在顺序串删除题上特别规律。我把它整理成一张表测试点类型输入特征考察内容正常删除非空串删除中段基本搬移逻辑删除头部/尾部pos1 或 poslength循环起点/终点的边界非法位置pos1 或 poslength参数校验完整性超长删除len 大于剩余长度合法性判断是否严密删空串length0 时调用删除空串处理大数据和全删长度很大、全为待删字符复杂度是否合格前两个测试点是“免费午餐”只要函数主体写完基本能过。从第三个开始考察的就是你删除前的参数校验写得完不完整。很多同学在“正常删除”用例上拿了满分却栽在pos1这种非法输入上就是因为函数里少了第一道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的输出会把残留字符一起带出来。我在实际调试中还有一个习惯写完函数先别急着提交自己构造三个用例——删除第一个字符、删除最后一个字符、删除后整个串变空串。这三个用例过了前三个测试点基本就稳了。等你在大数据测试点上碰了壁再回来想想快慢指针为什么比“边查边删”快应该就很有体感了。顺序串的删除算法说到底就是一次扎实的“重叠搬移”把这个动作想透后面学串的插入、合并、模式匹配都会顺畅很多。