推销产品怎样才能打动客户_网页设计代码平台_站长之家查询_站长论坛

设S为源串，P为模式串——字符串匹配指的是S是否包含P

m = S.size();
n = P.size();

朴素匹配法： O(m*n)

对于S中下标在【0，m-n】的字符，逐个向后遍历并于P进行比较。
复杂度较高。

哈希匹配法： O(m*n)

利用进制的思想将字符串转换到实数域，不同的字符串对应不同的hash值。计算所有符合条件的hash值，并于P的hash值比较即可。
复杂度较高。并且有可能产生哈希冲突，需要特殊判断处理。

Robin-Karp（滚动哈希优化）： O(m+n)

哈希法的优化版，利用滑动窗口的思想，将对于每个hash值的更新复杂度降到常数级：n->2，即减去第一个字符的值，加上后一个字符的值。
复杂度较低，也存在hash冲突，需特殊处理。

KMP： O(m+n)

主要在于next数组的计算，有点类似于预处理。next只与P有关，和S无关。
复杂度较低。

---

示例代码如下：

#include <iostream>  
#include <string>  
#include <vector>
#include <cmath>  #define seed 31  
#define mod 1000000007  
#define Size 1000
using namespace std;// Hash转换  
long Hash(const string& s) {long hash = 0;for (char ch : s) {hash = (hash * seed + ch) % mod; // 每次都取模  }return hash;
}// 朴素匹配法: O(m*n)  
void Match(const string& S, const string& P) {int m = S.size();int n = P.size();if (n == 0 || m < n) return; // 处理特殊情况  for (int i = 0; i <= m - n; i++) {int j = 0;while (j < n && S[i + j] == P[j]) {j++;}if (j == n) { // 完全匹配  cout << "Pattern found at index " << i << endl;}}
}// Hash匹配法: O(m*n)  
void HashMatch(const string& S, const string& P) {int m = S.size();int n = P.size();if (n == 0 || m < n) return; // 处理特殊情况  long hash_p = Hash(P);long hash_s[Size] = { 0 };for (int i = 0; i + n <= m; i++) {hash_s[i] = Hash(S.substr(i, n));}for (int i = 0; i <= m - n; i++) {if (hash_p == hash_s[i]) {// 再检查一次确保哈希碰撞不误报  if (S.substr(i, n) == P) {cout << "Pattern found at index " << i << endl;}}}
}// Robin-Karp算法: O(m+n) 使用滚动数组优化 
void HashMatchPlus(const string& S, const string& P) {int m = S.size();int n = P.size();if (n == 0 || m < n) return; // 处理特殊情况  long hash_p = Hash(P);long hash_s = Hash(S.substr(0, n));long seed_n = 1; // seed^n % mod  // 预计算seed^n  （可以用快速幂优化）——见快速幂算法for (int i = 0; i < n; i++) {seed_n = (seed_n * seed) % mod;}for (int i = 0; i <= m - n; i++) {if (hash_p == hash_s) { // 再来一次朴素匹配  if (S.substr(i, n) == P) {cout << "Pattern found at index " << i << endl;}}if (i < m - n) {hash_s = (hash_s * seed + S[i + n] - S[i] * seed_n) % mod; // 更新哈希  if (hash_s < 0) {hash_s += mod; // 确保哈希值为正  }}}
}// KMP算法: O(m+n)
vector<int> Next(const string& P) {int n = P.size();if (n == 0) return vector<int>{-1};if (n == 1) return vector<int>{-1, 0};vector<int>next(n, 0);next[0]= -1;next[1]= 0;int j = 1, k = next[j];while (j < n - 1) {if (k < 0 || P[j] == P[k]) {next[++j] = ++k;}else {k = next[k];}}return next; 
}void KMP(const string& S, const string& P) {int m = S.size();int n = P.size();if(m<n || n==0 || m==0) return;vector<int> next=Next(P);int i=0,j=0;while (i < m) {if (j<0 || S[i] == P[j]) {i++;j++;}else {j = next[j];}if (j == n) {cout << "Pattern found at index " << i-j << endl;i--;j = next[j-1];}}
}int main() {string S = "abcabcabcabcbcbcbbc";string P = "bc";cout << "Match: " << endl;Match(S, P);cout << "HashMatch: " << endl;HashMatch(S, P);cout << "HashMatchPlus: " << endl;HashMatchPlus(S, P);cout<<"KMP: "<< endl;KMP(S,P);return 0;
}