C字符串搜索和替换算法

最近需要利用C进行字符串的搜索和替换，发现C的标准库只有基本的搜索函数，并没有需要的搜索以及?替换的库，同时上网查了一下，发现有些小伙伴提供的算法太麻烦，比如替换的时候还要考虑替换字符的长短和数组收缩的问题，于是决定自己写一个，现在分享给大家！

（一）搜索并替换算法，strstr配合strncat函数

需要运用的标准库string.h中的strstr函数，strstr函数所做的动作就是搜索str1中是否包含str2的字符串并返回str2在str1中的指针位置，就是这么简单，但是已经很厉害了，基本解决了核心的搜索问题，接下来的应用需要创造的一个循环。循环中需要不断更新指针，让strstr函数从下一个位置开始，而这个下个位置就是上个位置偏移str2的长度，因为你不想重复搜索同一个位置两次。这样循环下来，所有在str1中匹配str2的位置都会被找到，解决了长字符串的搜索问题。

接下来看替换，如果替换的字符串和被替换的字符串长度一样都好办，但是如果短了或者长了，就有会数组不够用或者空格的问题。之前网上的算法是采用移位的方法来解决，但是在我看来这个有点麻烦了。为什么不换个角度想问题？我们完全可以不用在原字符串上折腾，重新建立一个新字符串，把需要的字符串提取出来进行拼接就好。利用strncat函数，需要就是两个指针，一个跟踪搜索字符串的起始位置（如图a的位置），一个跟踪下一个搜索到的位置（如图b的位置），而他们之间的偏移量（如图a-b）就是需要拼接到新字符串中的原字符串中的保留部分（把a-b拼接到A-B），然后紧接着在这个字符串的后边拼接上需要替换的字符串str3（如图B-C），如此循环直到最后一个部分。大家知道，循环的条件是下一个搜索为真，当到了字符串末尾的时候，如果末尾的字符串不包含需要搜索的字符串str2，这部分的拼接命令就被跳过了，为了补全这部分的内容，需要在跳出循环后再加一段最后的字符串补全命令。这样就完美了。最后把结果打印输出到标准输出。

新字符串需要动态内存分布，计算方式是如果替换的字符串长度比原来的短或相等，使用原来字符串的长度，如果比原来的长，则需要在原来字符串的基础上加上二者的长度差乘与最大可能替换的频率（即原字符串长度除以目标替换字符串的长度）。这比用数组好，因为可以到运行的时候才分配内存，即不用担心不够，也不用预留太多的数组空间，造成浪费。尤其是当我需要在单片机上运行函数，内存的资源是非常有限的。当然最后别忘了调用free（）函数，释放内存。

我的示例函数直接将结果打印到屏幕上，如果需要进行数据处理，可以修改函数，在函数参数中增加一个新字符串数组的指针，把上边的动态分布内存的程序放在主程序中而不是函数中就行了。

（二）分隔并替换算法，strtok配合strcat函数

strtok是一个很有意思的函数，平时用的并不多，它会搜索原字符串str1，并把目标字符串集合str2（group）中匹配的字符串作为分隔符号，并返回第一个被分隔的字符串。如果大家熟悉正则表达式，有点类似于【】方括弧号中的字符集，它的使用很特别，如果需要在while循环中使用，第二次的起始指针是NULL空指针。有了被分隔符返回的字符串，接下来的步骤和上一个算法很相似，就是在提取出的字符串后增加需要替换的字符串，并形成新的字符串。需要注意的是，strtok函数是会改变原字符串的，为了保护原字符串，复制了原字符串到临时变量。同时和上个算法不同的是，需要删除多余的末尾添加的替换字符串。

如果被替换的目标字符串在原字符串中是独一无二的，两种方法都有效，没有什么区别。但是如果 “Please%20input%20correct%20date%20in2021”，这是典型的HTTP传输字符串的编译代码，如果目标替换字符是%20，最后的2021中的20和2也会被替换掉，因为第二种算法把2和0都看作是需要搜索替换的目标字符串。但是如果你只是想达到泛搜索的目的，那第二种算法很方便。无需为每个可能的字符串单独调用函数了。

嵌入式开发需要考虑的首要因素是硬件的限制，无论是内存的空间还是CPU的能力，效能同时需要解决问题，虽然C没有那么丰富的库，但是标准库中的函数已经很强大了，剩下就需要小伙伴们根据需要自己开发了，配料都准备好了，烧什么菜自己决定吧！