发现好多笔试题，都问的是库函数。往简单的做，有效率不太高的算法，往复杂的做，就得看源码了。

写一个在一个字符串（n）中寻找一个子串（m）第一个位置的函数

暴力字符串匹配方法（Brute forceing matching）。这个写法不难，复杂度O(n*m)。

Rabin-Karp算法，能把复杂度最小减到O(n)。设要匹配的子串为sep，查找的字符串为s。通过一个哈希算法，把sep哈希成一个数字，以sep的长度，依次遍历s中长度和sep相同的串，直到计算出的值是相等的。

计算哈希的方法是，把原本的字符串看作是一种E进制的编码，然后将该编码转成10进制用数字表示。Golang用16777619作为该进制数。（这是我的理解，至于为什么选择这个整数，我也不是很清楚，只不过发现很多哈希算法都用过这个神奇的数字16777619 = (2^24 + 403)）。

1*E+2 != 4*E+5

这里有一个问题，如果要匹配的字串长度比较长，是1000位，那么，每一次匹配都得对这1000位进行计算。这时的复杂度就是O(n*m)了，而且还需要计算，这比暴力判断算法还要复杂。仔细观察，发现每次计算的长度的都一样，而且是依次进行的，前后两个串12和23有共同部分2，如果子串sep长度是1000，那么前后两次子串的共同部分就是999的长度了。所以，只需要保留共同部分，把前面的头去掉，后面的尾补上，就能够完成新串的计算。

(1*E+2)*E+3-1*E*E = 2*E+3
fori-n+1
unit32

本文所涉及到的完整源码请参考。

参考文献