本文共 1473 字，大约阅读时间需要 4 分钟。

#include <cstdlib>#include <iostream>#include <string>#include <vector>using namespace std;void getTab(string pat, vector<int> &vec){ int patLen = pat.size(); vec.push_back(-1); int i = 0, j = -1; while(i < patLen) { if(j == -1 || pat[i] == pat[j]) { i++; j++; if(pat[i] != pat[j]) vec.push_back(j); else vec.push_back(vec[j]); } else j = vec[j]; }}int find(string target, string pat){ vector<int> fTab; getTab(pat, fTab); int tarLen = target.size(); int patLen = pat.size(); int tarPos = 0, patPos = 0; while(tarPos < tarLen && patPos < patLen) { if(target[tarPos] == pat[patPos]) { tarPos++; patPos++; } else { if(fTab[patPos] == -1) { tarPos++; patPos = 0; } else patPos = fTab[patPos]; } } if(patPos < patLen) return -1; else return tarPos - patLen;}int main(int argc, char *argv[]){ string target, pat; cout << "please input the target string: " << endl; cin >> target; cout << "please input the patten string: " << endl; cin >> pat; int pos = find(target, pat); if(pos >= 0) cout << "find and pos is: " << pos << endl; else cout << "not found" << endl; system("PAUSE"); return EXIT_SUCCESS;} 

转载地址：http://tfkqb.baihongyu.com/