思想是将字符串转化为整数进行比较，采用取余数的hash函数进行转换，假设目标字符串长度为m，源字符串长度为n，（m<n），预处理阶段需要O（m）的时间，匹配时间是O((n-m+1)m)，预计运行时间为O（n+m）。 首先将原串中前m个字符，和目标串的值进行比较，若不形同，则向前移动一位，再次比较，相同时需采用朴素算法讲两个字符串逐位比较。下面是c++实现。
#include<iostream> #include<string> #include<Windows.h> using namespace std; int strstr(string sor, string tar) { int n = sor.length(); int m = tar.length(); int pow = 1,base=31; for (int i = 0; i < m; i++) { pow =( pow * 31) % base; } int tarhash = 0; for (int i = 0; i < m; i++) { tarhash = (tarhash * 31 + tar[i])% base; } int sorhash = 0; for (int i = 0; i < n; i++) { sorhash = (sorhash * 31 + sor[i]) % base; if (i < m - 1) continue; if (i >= m) { sorhash = sorhash - (sor[i - m] * pow) % base; if (sorhash < 0) sorhash += base; } if (tarhash == sorhash) { if (sor.substr(i - m + 1, m) == tar) { return i - m + 1; } } } } void main() { string a, b; cin >> a >> b; cout<<strstr(a, b); system("pause"); }