getNext是KMP算法找next的方法，getBetterNext是KMP改进方法。
    这个算法的核心想法就是在匹配的时候不走回头路

    1. #include <iostream>
    2. #include <vector>
    3. #include <string>
    5. int IndexKMP(std::string SrcStr, std::string tgtStr, int startIdx);
    6. void getNext(std::string tgtStr, std::vector<int>& next);
    7. void getBetterNext(std::string tgtStr, std::vector<int>& next);
    9. int main()
    10. {
    11.     std::string src = "Haymwanx_wangaAAAAAAAabziteng";
    12.     std::string tgt = "aAAAAAAAab";
    13.     std::cout << IndexKMP(src, tgt, 0);
    14. }
    16. int IndexKMP(std::string SrcStr, std::string tgtStr, int startIdx) {
    17.     int i = startIdx;
    18.     int j = 0;
    19.     std::vector<int> next(255);
    20.     getNext(tgtStr, next);
    21.     for (int i = 0; i < next.size(); i++) {
    22.         std::cout << next[i] << ' ';
    23.     }
    25.     std::cout << std::endl;
    26.     getBetterNext(tgtStr, next);
    27.     for (int i = 0; i < next.size(); i++) {
    28.         std::cout << next[i] << ' ';
    29.     }
    32.     while (i < SrcStr.size() && j < tgtStr.size()) {
    33.         if (SrcStr[i] == tgtStr[j]) {
    34.             ++j;
    35.             ++i;
    36.         }
    37.         else if (j==0){
    38.             ++i;
    39.             j = next[j];
    40.         }
    41.         else {
    42.             j = next[j];
    43.         }
    44.     }
    45.     if (j >= tgtStr.size()) {
    46.         return i - tgtStr.size();
    47.     }
    48.     else {
    49.         return 0;
    50.     }
    51. }
    53. void getBetterNext(std::string tgtStr,std::vector<int>& next) {
    54.     int i = 1, j = 0;
    55.     next[0] = 0;
    56.     while (i < tgtStr.size()) {
    57.         if (j == 0 || tgtStr[i] == tgtStr[j]) {
    59.             if (tgtStr[i] == tgtStr[j]) {
    60.                 next[i] = next[j];
    61.             }
    62.             else {
    63.                 next[i] = j;
    64.             }
    65.             ++i; ++j;
    66.         }
    67.         else {
    68.             j = next[j];
    69.         }
    70.     }
    71. }
    73. void getNext(std::string tgtStr, std::vector<int>& next) {
    74.     int i = 1, j = 0;
    75.     next[0] = 0;
    76.     while (i < tgtStr.size()) {
    77.         if (j == 0 || tgtStr[i] == tgtStr[j]) {
    78.             next[i] = j;
    79.             ++i; ++j;
    80.         }
    81.         else {
    82.             j = next[j];
    83.         }
    84.     }
    85. }