1.navite string 算法：
基本就是一个一个匹配，对于不太长的字串来说，效率还行。
效率：O ((n - m + 1)m )
算法伪代码：
NAIVE-STRING-MATCHER(T, P) 1 n ← length[T] 2 m ← length[P] 3 for s ← 0 to n - m 4 do if P[1 ‥ m] = T[s + 1 ‥ s + m] 5 then print "Pattern occurs with shift" s C语言实现： char* mmi_naive_string_match(char* T, char* P) { /*----------------------------------------------------------------*/ /* Local Variables */ /*-------------------------------------------------------------*/ int n,m,s; char *temp = NULL; bool ret = false; /*----------------------------------------------------------------*/ /* Code Body */ /*----------------------------------------------------------------*/ n = strlen(T); m = strlen(P); assert(m<=n); temp = (char*)malloc(m+1); memset(temp,0,m+1); for(s=0; s<n-m; s++) { memcpy(temp,T+s,m); if(0==strcmp(temp,P)) { ret = true; free(temp); temp = NULL; break; } } if(ret) { return (T+s); } else { return NULL; } } 2. Rabin-Karp 算法 主要思想是，如果字符串相同，则他们的和一定相同。由于字符串的和会超过32位，更进一步，他们和的模一定相同，既同余。 也就是排除法，先排除不可能的，在比较有可能的位置。 最坏情况： Θ((n - m + 1)m) 伪代码： RABIN-KARP-MATCHER(T, P, d, q) 1 n ← length[T] 2 m ← length[P] 3 h ← dm-1 mod q 4 p ← 0 5 t0 ← 0 6 for i ← 1 to m ▹ Preprocessing. 7 do p ← (dp + P[i]) mod q 8 t0 ← (dt0 + T[i]) mod q 9 for s ← 0 to n - m ▹ Matching. 10 do if p = ts 11 then if P[1 ‥ m] = T [s + 1 ‥ s + m] 12 then print "Pattern occurs with shift" s 13 if s < n - m 14 then ts+1 ← (d(ts - T[s + 1]h) + T[s + m + 1]) mod q d,q取任意质素， q ≥ m C语言实现： int mmi_power_local(int base, int m) { int i =0; int sum = 0; int temp =base; if(m>0) { for(i =1;i<m;i++) { temp = temp*base; } } else { assert(0); } return temp; } bool check_string_same(char* T, char*P,int len) { int i =0; for(i=0;i<len;i++) { if(T[i]!=P[i]) { return false; } } return true; } /************************************************************** *file name *mmi_rabin_karp_string_match *parameter *[in] T text string buffer *[in] P key string buffer *[in] d *[in] q modulo int * ***************************************************************/ void mmi_rabin_karp_string_match(char* T, char* P, int d, int q) { /*----------------------------------------------------------------*/ /* Local Variables */ /*-------------------------------------------------------------*/ int n,m,pp; int i,s,h = 0; int tt[MAX_SIZE] = {0}; /*----------------------------------------------------------------*/ /* Code Body */ /*----------------------------------------------------------------*/ n = strlen(T); m = strlen(P); h = mmi_power_local(d,m-1)%q; pp = 0; tt[0] = 0; for(i=0;i<m;i++) { pp = (d*pp+P[i])%q; tt[0] = (d*tt[0]+T[i])%q; } for(s =0;s<=n-m;s++) { if(pp == tt[s]) { if(check_string_same(&T[s],P,m)) { printf("the string occurs here,line is %d!!/n",s); } } if(s<n-m) { tt[s+1] = (d*(tt[s]-h*T[s])+T[s+m])%q; if(tt[s+1]<0) { tt[s+1]+=q; } } } }