Rabin-Karp子字符串查找算法

适合于strstr函数

我们要在字符串s(长度为n)里面寻找t(长度为k)

在s里面顺序遍历，由于计算长度与t相同的字串的hash值, 时间复杂度为O(k)， 所以后面一个字串的hash值可以是之前的字串在常数时间求得。

Brute-force时间复杂度为O(mn), KMP是O(m+n)

首先建立lookup table
a b a b c
0 0 1 2 0
j为当前的index, 如果不匹配，下一个去比较的index是a[j-1]

建立lookup table的方法类似于KMP
len = 0, 表示pattern的index, i为str的index

1. if(p[len] == str[i]) res[i] = len; i++, len++;
2. if(p[len]!=str[i]) {
   if(len!=0) len = res[len-1];
   else index++;
   }