#include <iostream> #include <string> using namespace std; int b_force_match(string str, string ptr) {     int i, j, temc;     int tlen = ptr.length();     int plen = str.length();     for (i = 0, j = 0; i <= plen - tlen; i++)     {         temc = i;         j = 0;         while (str[temc] == ptr[j] && j < tlen)         {             temc++;             j++;         }         if (j == tlen)             return i;     }     return -1; } void clnext(string str, int *next) {     int len=str.length();     next[0] = -1;     int k = -1;     for (int q = 1; q < len; q++)     {         while (k > -1 && str[k + 1] != str[q])             k = next[k];//回溯         if (str[k + 1] == str[q])            k++;         next[q] = k;     } } int KMP(string str,string ptr) {     int slen=str.length();     int plen=ptr.length();     int *next = new int[plen];     clnext(ptr, next);     int k = -1;     for (int i = 0; i < slen; i++)     {         while (k >-1&& ptr[k + 1] != str[i])             k = next[k];         if (ptr[k + 1] == str[i])             k = k + 1;         if (k == plen-1)         {             delete next;             return i-plen+1;         }     }     delete next;     return -1; } int main() {     string str = "ahraaahahafafderqhgadgdfghadfhnmym,,aryzkiababaabaftyacfabaou";     string ptr = "ababaabaf";     cout << "patternmatch" << endl;     cout << "b_force:" << endl;     cout << b_force_match(str, ptr) << endl;     cout<<"KMP:"<<endl;     cout << KMP(str, ptr) << endl;     return 0; }