删除子字符串

这是之前校招遇到的一道笔试题,整理下思路和代码。

问题:给定源字符串 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


阅读全文 »