1.首先是朴素匹配，实际上就是穷举：

用C语言实现的函数我放到这里：

（注意，为了方便将来移植，我的实现中所有函数都是被包含在POSIX的标准中的）?

这里说明上面两个我不熟悉的方法

2.Rabin-Karp算法

基本数论的概念不太懂，但是简单实现还是可以的，

因为此算法描述比较针对数字字符串进行匹配，我的实现主要就是针对手机号之类的数字来进行匹配，当然，具体描述还要看算法导论上的描述

（1）秦九韶/horner法则

（2）按照偏移量计算t的字串的数值大小

注意，其中的pow函数是自己写的一个简单函数而不是math.h中的函数：

（3）主算法：

（注意，tx的位置是我之前分配的空间，所以用完之后还是free掉为好）

下面是我在实现上述代码过程中不熟悉的一个函数描述：

测试用例：

（不出意外，这个就是我用来做拨号盘的匹配的算法了）

3.基于有限自动机的字符串匹配算法

这个自动机算法算是比较好理解的一个算法，因为我学过数字逻辑，课上有讲过有限自动机的原理，所谓有限自动机，就是在系统在有限情况下，任何状态的变化都在系统的有效循环内，在系统当前状态下，系统针对任意一个可预知的输入（比如我们知道系统输入只可能是0或1），都有一个有效的状态转移。

具体理论还请自行翻书，下面是我的实现，由于在构造状态转移函数的时候我没有自定义数据结构，而是选择了C++的map类型来存储的转移函数，所以下面使用的都是C++的基本语法，使用了auto表明我使用了C++11标准，Android NDK应该是支持的，下面是具体实现：

1.计算状态转移函数

这里我在map中查找的方法可能不是很正规，有好的方法请告诉我。

测试书中的用例的结果：

?记录下上述我不熟悉的函数：

4.KMP算法

在有限自动机的基础上，KMP是针对要匹配的字符串进行再次优化的一种方式。

因为有限自动机针对的是每个要匹配的字符串中的字符计算的转移函数。而KMP则是针对要匹配的字符串的字串来减少比较计算的。

比如ababaca这里，发现如果目标字符串与要匹配的字符串中的前5个字符匹配，那么如果根据朴素（穷举）法，我们只能后移一位来继续逐位比较，

但是可以看到的是，前五个字符的前两个字符正好是他自己的后缀，

这样，我们只需要将这两个作为已经匹配好的字符串，同时计算好此时在朴素法中的相对位移，那么就可以节约一大部分的比较时间。?

使用KMP，需要计算出匹配字符串本身的“转移函数”-后缀转移函数（模式的前缀函数），这个函数记录的是匹配字符串的前n个字符是前m个字符的后缀（m>n），因此，这个函数可以用一个映射来表示，同时每个m唯一（因为m是从0-匹配字符串长度的单步递增,step=1）。?

计算前缀函数的函数：

因为KMP很像朴素法，所以主算法中使用的就是结合前缀函数的一个类朴素匹配：

（为了好看，我输出改成了i-m+2，这里随便我们写）.?

测试书中示例的结果：

以上就是算法导论中主要介绍的字符串匹配算法，如果匹配大规模字符串，当然建议是KMP（虽然理解起来不太容易）。