字符串匹配算法随想

数论对于算法的妙用不仅仅是素性测试
还有一个很经典的问题——字符串匹配

常规的字符串匹配通过逐步移动匹配目标，模式 P的长度和文本规模决定了算法的计算规模。有一种叫做 卡普拉宾的算法，通过将字符转换成数字，然后用一种同余判定运算否定掉大部分不匹配的模式，这种算法和素性测试有异曲同工之妙。

不匹配判定，如果两个数字模一个素数不同余，那么它们肯定不相同，反之则未必，即如果两个数字同余，它们字符未必一样

另一个点，有限字符集总是可以转换成一种对应进制的数字
例如10进制的字符集是 {0, 1, 2, ..., 9} 十六进制是个16个字符集，增加 {a, b, c, d, e, f}
同理汉字，... ， 汉字可以转成一个万进制的数——这有点夸张，但是确实是可以做到的。

这个方法有效的另一个原因和素性测试算法一样——依赖于同余运算的高效

值得注意的是，对字符串生成摘要，过程类似很多的哈希函数，对应的操作很像，实际上拉宾卡普算法的思想有些地方也会描述成哈希函数法。