strings.go 里的那些骚操作

go version go1.11 darwin/amd64

/src/strings/strings.go

strings.go 文件中定义了近40个常用的字符串操作函数（公共函数）。以下是主要的几个函数。

函数简介

返回 在 中第一次出现的位置，不存在返回 ；采用算法

根据 把字符串 进行切分，返回切分后的数组

跟 功能刚好相反

返回字符串 重复 次得到的字符串

返回去除首尾存在于 的字符的切片

字符串替换

判断两个字符串代表的文件夹是否相等（忽略大小写）

以及 （ 函数把单词转换成标题形式，不是）。

还有一些以上函数派生出的其他函数。比如： 基本是通过 函数实现的；与 原理一致的 函数；与 有关的 等。

接下来，本文会对 函数进行分析。

ps: 返回的是字符串的字节数，不是字符数。字符数请使用

Index: RabinKarp 算法实现

, 返回 在 中第一次出现的位置，不存在返回 ；采用算法

函数会先对 的长度 进行判断，对特殊情况做快速处理。

其次，如果长度 以及 足够小，则使用算法：即暴力匹配，拿 与 进行比较，如果相等，返回 ，其中 …

最后，会先尝试暴力匹配，如果匹配失败次数超过临界点，则换成 算法。

（为了方便阅读，文中不放全部代码，只展示核心代码与部分结构代码）

在看 函数之前，我们先了解一下 算法。

算法是由 Robin 和 Karp 提出的字符串匹配算法。该算法在实际应用中有较好的表现。

算法的核心步骤：

// 大素数

对 构造 值。 ，

对 的每 个子串按照相同逻辑构造 值，判断与 的 是否相等；如果 相等，则比较子串是否真的与 相等

重复第三步，直到找到，或者未找到。

ps:

该算法之所以快，是因为 的 值可以由 的 值计算出。即

另外， 计算 时并没有 ，而是定义了 为 类型，利用整型溢出实现了对 取模的效果。（一般来说是对另一个大素数取模，显然这里不是，不过毕竟这么大的数也没啥大影响）

该算法预处理时间为 ， 为 ，运行最坏时间为 ， 为 。最坏情况为每个子串的 都与 的一样。在平均情况下，运行时间还是很好的。

除了 算法外，还要一些其他的字符串匹配算法。《算法》导论中介绍了另外两种优秀的算法，分别是 与 算法（即 算法），这两个算法的运行时间都为 。

下面是 函数

函数跟计算 的 逻辑一致。不过不得不提一下 的计算方法。

以上是 函数的实现逻辑。

Trim: 出神入化的位操作

返回去除首尾存在于 的字符的切片。

的本质逻辑也比较简单：

根据 构造一个函数，该函数签名为 ，接受一个 类型的值，返回该值是否在 中

然后调用 ；这两个函数调用了 ，其逻辑也比较简单，不再赘述

函数 就是刚才提到的构造 判断 值是否在 中的函数 的函数。

其中，最有意思的要数 函数，该函数用了一个 数组实现了 128 个 码的 表。

以上是 函数及其位操作。

从 Join、Repeat、Replace 看字符串如何高效生成

这三个函数的逻辑都很简单，不再赘述。

频繁申请内存是很耗费时间的，所以在生成某个字符串时，如果能够预知字符串的长度，就能直接申请对应长度的内存，然后调用 函数把字符复制到对应位置，最后把 强转成字符串类型即可。

以上是关于生成字符串时避免多次分配内存的高效做法。

Y_xx