这是之前校招遇到的一道笔试题，整理下思路和代码。
问题：给定源字符串 pSrc 和待删除的字符串 pDel，要求将 pSrc 中所有出现的 pDel 删除。
因为是让现场给代码，第一次给出每次用 KMP 查找到 pDel 后删除，后面的字符串向后移动。这样会造成重复移动的情况。
思路
查找当前 pDel 出现的位置 pFirst，用一个计数器记录当前是第几次找到 pDel（假设为 n），结合 pDel 的长度 len，然后查找下一个 pDel 所在的位置 pSecond。如此 pFirst 和 pSecond 之间的字符串只需直接向后移动 n * len 距离，一次移动即可。
假设当前 pFirst 指向第6个字符，n 为2，pSecond 指向第11个字符，len 为2，那么只需将第 6+2=8 到第 11-1=10 个字符向后移动 2*2=4 个位置即可，如下图所示：
如图所示，第一次执行 KMP 返回1，然后查找下一次出现的位置，再次执行 KMP 返回6，所以第 1+2=3 ~ 6-1=5 个字符（即图中①部分）向后移动 12=2 个位置；再次执行 KMP 返回11，则第 6+2=8 ~ 11-1=10 个字符（即图中②部分）向后移动 22=4 个位置；重复执行 KMP 发现源字符串中已经没有 pDel，则将第 11+2=13 ~ 最后一个字符（即图中③部分）向后移动 3*2=6 个位置。
最终代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <stdio.h> #include <string.h> #include "kmp.c" void StrMoveBehind(char *str, int count, int offset) { if(str==NULL || count<=0 || offset<=0) return; while(count>0) { *(str-offset) = *str; ++str; --count; } } /* 删除pSrc中的所有pDel，每次删除一个，count记录当前删除次数，从而保证每个字符只移动1次。 */ void DeleteStr(char *pSrc, char *pDel) { if(pSrc==NULL || pDel==NULL) return; int count = 0; int lenDel = strlen(pDel); int lenSrc = strlen(pSrc); int index[2] = {0, 0}; int flag = 0; char *p = pSrc; index[flag] = KMP(p, pDel, lenSrc, lenDel); while(index[flag]!=-1) { ++count; p += index[flag]+lenDel; index[1-flag] = KMP(p, pDel, strlen(p), lenDel); if(index[1-flag]!=-1) StrMoveBehind(p, index[1-flag], count*lenDel); else StrMoveBehind(p, strlen(p), count*lenDel); flag = 1-flag; } pSrc[lenSrc-count*lenDel] = ''; } int main(void) { char pSrc1[] = {"tell hello elle"}; char pDel1[] = {"el"}; DeleteStr(pSrc1, pDel1); printf("%sn", pSrc1); char pSrc2[] = {"tell hello elle"}; char pDel2[] = {"non"}; DeleteStr(pSrc2, pDel2); printf("%sn", pSrc2); return 0; } |
代码中使用一个2元素整数数组记录当前找到的 pDel 位置和下一个 pDel 在 pSrc 中的位置。count 记录当前是第几次移动。StrMoveBehind 函数用来移动元素。注意，该函数并不移动最后一个 ”，所以需要在 DeleteStr 最后为新字符串添加该字符。
该程序不需要额外的存储空间，也可以申请额外的空间采用空间换时间的方法，将新字符串复制到新建的字符数组中，也可以避免字符串的重复移动。
KMP 算法和本程序的实现代码均保存在在我的 github 上。
KMP： https://github.com/knd2/basic_algorithm/blob/master/stringprocess/kmp.c
注：转载注明出处并联系作者，本文链接：https://nodefe.com/delete-substring/