{"id":255,"date":"2012-11-12T14:01:00","date_gmt":"2012-11-12T06:01:00","guid":{"rendered":"http:\/\/nike0good.jp1.rpvhost.net\/160"},"modified":"2012-11-12T14:01:00","modified_gmt":"2012-11-12T06:01:00","slug":"kmp","status":"publish","type":"post","link":"https:\/\/nike0good.com\/?p=255","title":{"rendered":"KMP"},"content":{"rendered":"

\n\u4f5c\u8005\uff1aJuly\u3002
\n\u51fa\u5904\uff1ahttp:\/\/blog.csdn.net\/v_JULY_v\/<\/a>\u3002\n<\/p>\n

\n<\/a>\u5f15\u8bb0<\/h3>\n

\n    \u6b64\u524d\u4e00\u5929\uff0c\u4e00\u4f4dMS\u7684\u670b\u53cb\u9080\u6211\u4e00\u8d77\u53bb\u4e0e\u4ed6\u8ba8\u8bba\u5feb\u901f\u6392\u5e8f\uff0c\u7ea2\u9ed1\u6811\uff0c\u5b57\u5178\u6811\uff0cB\u6811\u3001\u540e\u7f00\u6811\uff0c\u5305\u62ec<\/span>KMP\u7b97\u6cd5\uff0c\u552f\u72ec\u5728\u8bb2\u89e3<\/span>KMP\u7b97\u6cd5\u7684\u65f6\u5019\uff0c\u8a00\u8bed\u78d5\u78d5\u78b0\u78b0\uff0c\u6211\u60f3\uff0c\u539f\u56e0\u6709\u4e8c\uff1a<\/span>1\u3001\u535a\u5ba2\u5185\u7684\u4e1c\u897f\u4e0d\u5e38\u56de\u987e\uff0c\u5fd8\u4e86\u4e0d\u5c11\uff1b<\/span>2\u3001\u4fbf\u662f\u6211\u5bf9<\/span>KMP\u7b97\u6cd5\u7684\u7406\u89e3\u8fd8\u4e0d\u591f\u5f7b\u5e95\uff0c\u81ea\u4e0d\u7528\u8bf4\u8bb2\u89e3\u81ea\u5982\uff0c\u8fd0\u7528\u81ea\u5982\u4e86\u3002\u6240\u4ee5\uff0c\u7279\u518d\u5199\u672c\u7bc7\u6587\u7ae0\u3002\u7531\u4e8e\u6b64\u524d\uff0c\u4e2a\u4eba\u5df2\u7ecf\u5199\u8fc7\u5173\u4e8e<\/span>KMP\u7b97\u6cd5\u7684\u4e24\u7bc7\u6587\u7ae0\uff0c\u6240\u4ee5\uff0c\u672c\u6587\u540d\u4e3a\uff1a<\/span>KMP\u7b97\u6cd5\u4e4b\u603b\u7ed3\u7bc7\u3002<\/span><\/p>\n

\n   \u672c\u6587\u5206\u4e3a\u5982\u4e0b\u516d\u4e2a\u90e8\u5206\uff1a<\/p>\n

    \n
  1. \u7b2c\u4e00\u90e8\u5206\u3001\u518d\u6b21\u56de\u987e\u666e\u901a\u7684BF\u7b97\u6cd5\u4e0e<\/span>KMP\u7b97\u6cd5\u5404\u81ea\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u5e76\u4e24\u76f8\u5bf9\u7167\u5404\u81ea\u7684\u5339\u914d\u539f\u7406\uff1b<\/span><\/li>\n
  2. \u7b2c\u4e8c\u90e8\u5206\u3001\u901a\u8fc7\u6211\u6b64\u524d\u7b2c\u4e8c\u7bc7\u6587\u7ae0\u7684\u5f15\u7528\uff0c\u7528\u56fe\u4ece\u5934\u5230\u5c3e\u8be6\u7ec6\u9610\u8ff0<\/span>KMP\u7b97\u6cd5\u4e2d\u7684<\/span>next\u6570\u7ec4\u6c42\u6cd5\uff0c\u5e76\u8fd0\u7528\u6c42\u5f97\u7684<\/span>next\u6570\u7ec4\u5199\u51fa<\/span>KMP\u7b97\u6cd5\u7684\u6e90\u7801\uff1b<\/span><\/li>\n
  3. \u7b2c\u4e09\u90e8\u5206\u3001KMP\u7b97\u6cd5\u7684\u4e24\u79cd\u5b9e\u73b0\uff0c\u4ee3\u7801\u5b9e\u73b0\u4e00\u662f\u6839\u636e\u672c\u4eba\u5173\u4e8eKMP\u7b97\u6cd5\u7684\u7b2c\u4e8c\u7bc7\u6587\u7ae0\u6240\u5199\uff0c\u4ee3\u7801\u5b9e\u73b0\u4e8c\u662f\u6839\u636e\u672c\u4eba\u7684\u5173\u4e8eKMP\u7b97\u6cd5\u7684\u7b2c\u4e00\u7bc7\u6587\u7ae0\u6240\u5199\uff1b<\/span><\/li>\n
  4. \u7b2c\u56db\u90e8\u5206\u3001\u6d4b\u8bd5\uff0c\u5206\u522b\u5bf9\u7b2c\u4e09\u90e8\u5206\u7684\u4e24\u79cd\u5b9e\u73b0\u4e2dnext\u6570\u7ec4\u7684\u6c42\u6cd5\u8fdb\u884c\u6d4b\u8bd5\uff0c\u6316\u6398\u5176\u533a\u522b\u4e4b\u6240\u5728\uff1b<\/span><\/li>\n
  5. \u7b2c\u4e94\u90e8\u5206\u3001KMP\u5b8c\u6574\u51c6\u786e\u6e90\u7801\uff0c\u7ed9\u51faKMP\u7b97\u6cd5\u7684\u51c6\u786e\u7684\u5b8c\u6574\u6e90\u7801\uff1b<\/span><\/li>\n
  6. \u7b2c\u516d\u6b65\u4efd\u3001\u4e00眼\u770b\u51fa\u5b57\u7b26\u4e32\u7684next\u6570\u7ec4\u5404值\uff0c\u901a\u8fc7\u51e0\u4e2a\u4f8b\u5b50\uff0c\u8ba9\u8bfb\u8005\u80fd\u6839\u636e\u5b57\u7b26\u4e32\u672c\u8eab\u4e00眼\u5224\u65ad\u51fa\u5176next\u6570\u7ec4\u5404值\u3002<\/span><\/li>\n<\/ol>\n

    \n    \u529b\u6c42\u8ba9\u6b64\u6587\u5f7b\u5e95\u8ba9\u8bfb\u8005\u6d1e\u7a7f\u6b64<\/span>KMP\u7b97\u6cd5\uff0c\u6240\u6709\u539f\u7406\uff0c\u6765\u9f99\u53bb\u8109\uff0c\u8ba9\u8bfb\u8005\u641e\u4e2a\u901a\u901a\u900f\u900f\uff08\u6ce8\u610f\uff0c\u672c\u6587\u4e2d\u7b2c\u4e8c\u90e8\u5206\u53ca\u7b2c\u4e09\u90e8\u5206\u7684\u4ee3\u7801\u5b9e\u73b0\u4e00\u7684\u5b57\u7b26\u4e32\u4e0b\u6807i \u4ece0<\/span>\u5f00\u59cb\u8ba1\u7b97\uff0c\u5176\u5b83\u90e8\u5206\u5982\u7b2c\u4e09\u90e8\u5206\u7684\u4ee3\u7801\u5b9e\u73b0\u4e8c\uff0c\u7b2c\u4e94\u90e8\u5206\uff0c\u548c\u7b2c\u516d\u90e8\u5206\u7684\u5b57\u7b26\u4e32\u4e0b\u6807i \u7686\u662f\u4ece1\u5f00\u59cb\u7684\uff09\u3002<\/span><\/p>\n

    <\/span><\/span><\/p>\n

    \n    \u5728\u770b\u672c\u6587\u4e4b\u524d\uff0c\u4f60\u5fc3\u4e2d\u5982\u82e5\u5bf9\u524d\u7f00\u548c\u540e\u7f00\u8fd9\u4e2a\u4e24\u4e2a\u6982\u5ff5\u6709\u81ea\u5df1\u7684\u7406\u89e3\uff0c\u4fbf\u6700\u597d\u4e86\u3002\u6709\u4e9b\u4e1c\u897f\u6bd4\u5982\u6b64KMP\u7b97\u6cd5\u9700\u8981\u6211\u4eec\u53cd\u590d\u601d\u8003\uff0c\u53cd\u590d\u6c42\u89e3\u624d\u884c\u3002\u4e2a\u4eba\u5199\u7684\u5173\u4e8eKMP\u7b97\u6cd5\u7684\u7b2c\u4e8c\u7bc7\u6587\u7ae0\u4e3a\uff1a\u516d\uff08\u7eed\uff09\u3001\u4eceKMP\u7b97\u6cd5\u4e00\u6b65\u4e00\u6b65\u8c08\u5230BM\u7b97\u6cd5<\/a><\/span>\uff1b\u7b2c\u4e00\u7bc7\u4e3a\uff1a\u516d\u3001\u6559\u4f60\u521d\u6b65\u4e86\u89e3KMP\u7b97\u6cd5\u3001updated\uff08\u6587\u672b\u94fe\u63a5\uff09\u3002ok\uff0c\u82e5\u6709\u4efb\u4f55\u95ee\u9898\uff0c\u6073\u8bf7\u4e0d\u541d\u6307\u6b63\u3002\u591a\u8c22\u3002<\/span><\/p>\n

    \n<\/a>\u7b2c\u4e00\u90e8\u5206\u3001KMP\u7b97\u6cd5\u521d\u89e3<\/span><\/h3>\n

    \n1\u3001<\/span>\u666e\u901a\u5b57\u7b26\u4e32\u5339\u914dBF\u7b97\u6cd5\u4e0e<\/span>KMP\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u6bd4\u8f83<\/span><\/strong><\/p>\n

    \n    KMP\u7b97\u6cd5\u662f\u4e00\u79cd\u7ebf\u6027\u65f6\u95f4\u590d\u6742\u7684\u5b57\u7b26\u4e32\u5339\u914d\u7b97\u6cd5\uff0c\u5b83\u662f\u5bf9<\/span>BF\u7b97\u6cd5\uff08<\/span>Brute-Force\uff0c\u6700\u57fa\u672c\u7684\u5b57\u7b26\u4e32\u5339\u914d\u7b97\u6cd5\u7684\uff09\u6539\u8fdb\u3002\u5bf9\u4e8e\u7ed9\u7684\u539f\u59cb\u4e32<\/span>S\u548c\u6a21\u5f0f\u4e32<\/span>P\uff0c\u9700\u8981\u4ece\u5b57\u7b26\u4e32<\/span>S\u4e2d\u627e\u5230\u5b57\u7b26\u4e32<\/span>P\u51fa\u73b0\u7684\u4f4d\u7f6e\u7684\u7d22\u5f15\u3002<\/span><\/p>\n

    \n
    \n

    BF\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/span>O(strlen(S) * strlen(T))\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6<\/span>O(1)\u3002<\/span><\/p>\n<\/div>\n<\/blockquote>\n

    \n
    \n

    KMP\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/span>O(strlen(S) + strlen(T))\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6<\/span>O(strlen(T))\u3002<\/span><\/p>\n<\/div>\n<\/blockquote>\n

    \n

    2\u3001<\/span>BF\u7b97\u6cd5\u4e0e<\/span>KMP\u7b97\u6cd5\u7684\u533a\u522b<\/span><\/strong><\/p>\n

        \u5047\u8bbe\u73b0\u5728S\u4e32\u5339\u914d\u5230<\/span>i\u4f4d\u7f6e\uff0c<\/span>T\u4e32\u5339\u914d\u5230<\/span>j\u4f4d\u7f6e\u3002\u90a3\u4e48\u603b\u7684\u6765\u8bf4\uff0c\u4e24\u79cd\u7b97\u6cd5\u7684\u4e3b\u8981\u533a\u522b\u5728\u4e8e\u5931\u914d\u7684\u60c5\u51b5\u4e0b\uff0c\u5bf9<\/span>\"[j]\"\u7684值\u505a\u7684\u5904\u7406<\/span>\uff1a<\/span><\/p>\n

       BF\u7b97\u6cd5\u4e2d\uff0c\u5982\u679c\u5f53\u524d\u5b57\u7b26\u5339\u914d\u6210\u529f\uff0c\u5373<\/span>s[i+j] == T[j]\uff0c\u4ee4<\/span>j++\uff0c\u7ee7\u7eed\u5339\u914d\u4e0b\u4e00\u4e2a\u5b57\u7b26\uff1b\u5982\u679c\u5931\u914d\uff0c\u5373<\/span>S[i + j] != T[j]\uff0c\u9700\u8981\u8ba9<\/strong><\/span>i++,\u5e76\u4e14<\/span>j=
    \n 0<\/strong>\uff0c\u5373\u6bcf\u6b21\u5339\u914d\u5931\u8d25\u7684\u60c5\u51b5\u4e0b\uff0c\u6a21\u5f0f\u4e32<\/span>T\u76f8\u5bf9\u4e8e\u539f\u59cb\u4e32<\/span>S\u5411\u53f3\u79fb\u52a8\u4e86\u4e00\u4f4d\u3002<\/span><\/p>\n

        \u800cKMP\u7b97\u6cd5\u4e2d\uff0c\u5982\u679c\u5f53\u524d\u5b57\u7b26\u5339\u914d\u6210\u529f\uff0c\u5373<\/span>S[i]==T[j]\uff0c\u4ee4<\/span>i++\uff0c<\/span>j++\uff0c\u7ee7\u7eed\u5339\u914d\u4e0b\u4e00\u4e2a\u5b57\u7b26\uff1b\u5982\u679c<\/span>\u5339\u914d\u5931\u8d25\uff0c\u5373S[i] != T[j]\uff0c\u9700\u8981\u4fdd\u6301<\/span>i\u4e0d\u53d8\uff0c\u5e76\u4e14\u8ba9<\/span>j
    \n = next[j]\uff0c\u8fd9\u91cc<\/span>next[j] <=j -1\uff0c\u5373\u6a21\u5f0f\u4e32<\/span>T\u76f8\u5bf9\u4e8e\u539f\u59cb\u4e32<\/span>S\u5411\u53f3\u79fb\u52a8\u4e86\u81f3\u5c11<\/span>1\u4f4d<\/span>(\u79fb\u52a8\u7684\u5b9e\u9645\u4f4d\u6570<\/strong><\/span>j
    \n - next[j]  >=1<\/strong>),<\/p>\n

        \u540c\u65f6\u79fb\u52a8\u4e4b\u540e\uff0ci\u4e4b\u524d\u7684\u90e8\u5206\uff08\u5373<\/span>S[i-j+1 ~ i-1]\uff09\uff0c\u548c<\/span>j=next[j]\u4e4b\u524d\u7684\u90e8\u5206\uff08\u5373<\/span>T[0 ~ j-2]<\/u>\uff09\u4ecd\u7136\u76f8\u7b49<\/u>\u3002\u663e\u7136\uff0c\u76f8\u5bf9\u4e8e<\/span>BF\u7b97\u6cd5\u6765\u8bf4\uff0c<\/span>KMP\u79fb\u52a8\u66f4\u591a\u7684\u4f4d\u6570\uff0c\u8d77\u5230\u4e86\u4e00\u4e2a\u52a0\u901f\u7684\u4f5c\u7528\uff01 <\/span>(\u5931\u914d\u7684\u7279\u6b8a\u60c5\u5f62\uff0c\u4ee4<\/span>j=next[j]\u5bfc\u81f4<\/span>j==0\u7684\u65f6\u5019\uff0c\u9700\u8981\u5c06<\/span>i
    \n ++\uff0c\u5426\u5219\u6b64\u65f6\u6ca1\u6709\u79fb\u52a8\u6a21\u5f0f\u4e32)\u3002<\/span>\n<\/p>\n

    3\u3001BF\u7b97\u6cd5\u4e3a\u4ec0\u4e48\u8981\u56de\u6eaf<\/span><\/strong><\/p>\n<\/div>\n

    \n\u9996\u5148\u8bf4\u4e00\u4e0b\u4e3a\u4ec0\u4e48BF\u7b97\u6cd5\u8981\u56de\u6eaf\u3002\u5982\u4e0b\u4e24\u5b57\u7b26\u4e32\u5339\u914d\uff08\u6070\u5982\u4e0a\u9762\u6240\u8ff0\uff1aBF\u7b97\u6cd5\u4e2d\uff0c\u5982\u679c\u5f53\u524d\u5b57\u7b26\u5339\u914d\u6210\u529f\uff0c\u5373s[i+j] == T[j]<\/span>\uff0c\u4ee4j++<\/span>\uff0c\u7ee7\u7eed\u5339\u914d\u4e0b\u4e00\u4e2a\u5b57\u7b26\uff09\uff1a<\/span><\/p>\n

    \n<\/span>      i+j\uff08<\/span>j\u968f<\/span>T\u4e2d\u7684<\/span>j++\u53d8\uff0c\u800c\u52a8\uff09<\/span><\/p>\n

    \n<\/span>S\uff1aaaaa<\/span>cefghij<\/p>\n

    \n   <\/span>      j++<\/p>\n

    \n<\/span>T\uff1aaaac<\/span> <\/p>\n

    \n\u5982\u679c\u4e0d\u56de\u6eaf\u7684\u8bdd\u5c31\u662f\u4ece\u4e0b\u4e00\u4f4d\u5f00\u59cb\u6bd4\u8d77\uff1a<\/p>\n

    \n<\/span>aaaac<\/span>efghij<\/p>\n

    \n<\/span>        a<\/span>aac<\/p>\n

    \n\u770b\u5230\u4e0a\u9762\u7ea2\u989c\u8272\u7684\u6ca1\uff0c\u5982\u679c\u4e0d\u56de\u6eaf\u7684\u8bdd\uff0c\u90a3\u4e48\u4ecea \u7684\u4e0b\u4e00\u4f4d<\/span>c \u6bd4\u8d77\u3002\u7136\u800c\u4e0b\u8ff0\u8fd9\u79cd\u60c5\u51b5\u5c31\u6f0f\u4e86\uff08\u6b63\u786e\u7684\u505a\u6cd5\u5f53\u7136\u662f\u8981\u56de\u6eaf\uff1a\u5982\u679c\u5931\u914d\uff0c\u5373S[i + j] != T[j]<\/span>\uff0c\u9700\u8981\u8ba9<\/strong>i++,\u5e76\u4e14<\/span>j=
    \n 0<\/span>\uff09\uff1a<\/span><\/p>\n

    \n<\/span>aaaac<\/u>efghij<\/p>\n

    \n<\/span>  aaac<\/span><\/p>\n

    \n

        \u6240\u4ee5\uff0cBF\u7b97\u6cd5\u8981\u56de\u6eaf\uff0c\u5176\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n

    \n
    \n
    \nview plain<\/a><\/div>\n<\/div>\n
      \n
    1. \nint<\/span> Index(SString S, SString T, <\/span>int<\/span> pos) {  <\/span><\/span><\/li>\n
    2. \n   \/\/\u8fd4\u56deT\u5728S\u4e2d\u7b2cpos\u4e2a\u5b57\u7b26\u4e4b\u540e\u7684\u4f4d\u7f6e<\/span>  <\/span><\/span><\/li>\n
    3. \n   i=pos; j=1;k=0;  <\/span><\/li>\n
    4. \n  while<\/span> ( i< = S[0] && j< = T[0] ) {  <\/span><\/span><\/li>\n
    5. \n      if<\/span> (S[i+k] = = T[j] ) {++k;  ++j;}   <\/span>\/\/\u7ee7\u7eed\u6bd4\u8f83\u540e\u7eed\u5b57\u7b26<\/span>  <\/span><\/span><\/li>\n
    6. \n      else<\/span> {i=i+1;   j=1; k=0;}      <\/span>\/\/\u6307\u9488\u56de\u6eaf\u5230 \u4e0b\u4e00\u9996\u4f4d\uff0c\u91cd\u65b0\u5f00\u59cb<\/span>  <\/span><\/span><\/li>\n
    7. \n  }  <\/span><\/li>\n
    8. \n  if<\/span>(j>T[0]) <\/span>return<\/span> i;          <\/span>\/\/\u5b50\u4e32\u7ed3\u675f\uff0c\u8bf4\u660e\u5339\u914d\u6210\u529f<\/span>  <\/span><\/span><\/li>\n
    9. \n  else<\/span> <\/span>return<\/span>  0;  <\/span><\/span><\/li>\n
    10. \n}\/\/Index<\/span>  <\/span><\/span><\/li>\n<\/ol>\n<\/div>\n

        \u4e0d\u8fc7\uff0c\u4e5f\u6709\u7279\u6b8a\u60c5\u51b5\u53ef\u4ee5\u4e0d\u56de\u6eaf\uff0c\u5982\u4e0b\uff1a
      \n<\/span>abcdefghij(\u4e3b\u4e32<\/span>)
      \n<\/span>abcdefg(\u6a21\u5f0f\u4e32<\/span>)
      \n  \u5373(\u6a21\u5f0f\u4e32<\/span>)\u6ca1\u6709\u76f8\u540c\u7684\u624d\u4e0d\u9700\u8981\u56de\u6eaf\u3002<\/span><\/p>\n

      \n4\u3001<\/span>KMP \u7b97\u6cd5\u601d\u60f3<\/span><\/strong>
      \n    \u666e\u901a\u7684\u5b57\u7b26\u4e32\u5339\u914d\u7b97\u6cd5\u5fc5\u987b\u8981\u56de\u6eaf\u3002\u4f46\u56de\u6eaf\u5c31\u5f71\u54cd\u4e86\u6548\u7387\uff0c\u56de\u6eaf\u662f\u7531T\u4e32\u672c\u8eab\u7684\u6027\u8d28\u51b3\u5b9a\u7684\uff0c\u662f\u56e0\u4e3aT\u4e32\u672c\u8eab\u6709\u524d\u540e'\u90e8\u5206\u5339\u914d'\u7684\u6027\u8d28\u3002\u50cf\u4e0a\u9762\u6240\u8bf4\u5982\u679c\u4e3b\u4e32\u4e3aabcdef\u8fd9\u6837\u7684\uff0c\u5927\u6ca1\u6709\u56de\u6eaf\u7684\u5fc5\u8981\u3002<\/p>\n

          \u6539\u8fdb\u7684\u5730\u65b9\u4e5f\u5c31\u662f\u8fd9\u91cc\uff0c\u6211\u4eec\u4eceT\u4e32\u672c\u8eab\u51fa\u53d1\uff0c\u4e8b\u5148\u5c31\u627e\u51c6\u4e86<\/span>T\u81ea\u8eab\u524d\u540e\u90e8\u5206\u5339\u914d\u7684\u4f4d\u7f6e\uff0c\u90a3\u5c31\u53ef\u4ee5\u6539\u8fdb\u7b97\u6cd5\u3002<\/span><\/p>\n

          \u5982\u679c\u4e0d\u7528\u56de\u6eaf\uff0c\u90a3\u6a21\u5f0f\u4e32\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\u4ece\u54ea\u91cc\u5f00\u59cb\u5462\uff1f<\/p>\n

          \u8fd8\u662f\u4e0a\u9762\u90a3\u4e2a\u4f8b\u5b50\uff0cT(\u6a21\u5f0f\u4e32<\/span>)\u4e3a<\/span>ababc\uff0c\u5982\u679c<\/span>c\u5931\u914d\uff0c\u90a3\u5c31\u53ef\u4ee5\u5f80\u524d\u79fb\u5230<\/span>aba\u6700\u540e\u4e00\u4e2a<\/span>a\u7684\u4f4d\u7f6e\uff0c\u50cf\u8fd9\u6837\uff1a<\/span><\/p>\n<\/div>\n

      \n
      \n

      ...ababd...<\/p>\n<\/div>\n

      \n

         ababc<\/p>\n<\/div>\n

      \n

          ->ababc<\/p>\n<\/div>\n<\/blockquote>\n

      \n

      \u8fd9\u6837i\u4e0d\u7528\u56de\u6eaf\uff0c<\/span>j\u8df3\u5230\u524d<\/span>2\u4e2a\u4f4d\u7f6e\uff0c\u7ee7\u7eed\u5339\u914d\u7684\u8fc7\u7a0b\uff0c\u8fd9\u5c31\u662f<\/span>KMP\u7b97\u6cd5\u6240\u5728\u3002\u8fd9\u4e2a\u5f53<\/span>T[j]\u5931\u914d\u540e\uff0c<\/span>j \u5e94\u8be5\u5f80\u524d\u8df3\u7684值\u5c31\u662f<\/span>j\u7684<\/span>next值<\/span>\uff0c\u5b83\u662f\u7531T\u4e32\u672c\u8eab\u56fa\u6709\u51b3\u5b9a\u7684\uff0c\u4e0e<\/span>S\u4e32<\/span>(\u4e3b\u4e32<\/span>)\u65e0\u5173<\/span><\/strong>\u3002<\/p>\n

      \n5\u3001next\u6570\u7ec4\u7684\u542b\u4e49<\/span><\/strong><\/p>\n

      \u91cd\u70b9\u6765\u4e86\u3002\u4e0b\u9762\u89e3\u91ca\u4e00\u4e0bnext\u6570\u7ec4\u7684\u542b\u4e49<\/span>\uff0c\u8fd9\u4e2a\u4e5f\u662fKMP\u7b97\u6cd5\u4e2d\u6bd4\u8f83\u4e0d\u597d\u7406\u89e3\u7684\u4e00\u70b9\u3002<\/span><\/p>\n

        \u4ee4\u539f\u59cb\u4e32\u4e3a: S[i]\uff0c\u5176\u4e2d<\/span>0<=i<=n\uff1b\u6a21\u5f0f\u4e32\u4e3a<\/span>: T[j]\uff0c\u5176\u4e2d<\/span>0<=j<=m\u3002<\/span><\/p>\n

        \u5047\u8bbe\u76ee\u524d\u5339\u914d\u5230\u5982\u4e0b\u4f4d\u7f6e<\/p>\n

                     S0,S1,S2,...,Si-j,Si-j+1...............,Si-1<\/span>, Si<\/span>, Si+1,....,Sn<\/p>\n

                                         T0,T1,.....................,Tj-1<\/span>, Tj<\/span>, ..........<\/p>\n

        S\u548c<\/span>T\u7684\u7eff\u8272\u90e8\u5206\u5339\u914d\u6210\u529f\uff0c\u6070\u597d\u5230<\/span>Si\u548c<\/span>Tj\u7684\u65f6\u5019\u5931\u914d\uff0c\u5982\u679c\u8981\u4fdd\u6301<\/span>i\u4e0d\u53d8\uff0c\u540c\u65f6\u8fbe\u5230\u8ba9\u6a21\u5f0f\u4e32<\/span>T\u76f8\u5bf9\u4e8e\u539f\u59cb\u4e32<\/span>S\u53f3\u79fb\u7684\u8bdd\uff0c\u53ef\u4ee5\u66f4\u65b0<\/span>j\u7684值\uff0c\u8ba9<\/span>Si\u548c\u65b0\u7684<\/span>Tj\u8fdb\u884c\u5339\u914d\uff0c\u5047\u8bbe\u65b0\u7684<\/span>j\u7528<\/span>next[j]\u8868\u793a\uff0c\u5373\u8ba9<\/span>Si\u548c<\/span>next[j]\u5339\u914d\uff0c\u663e\u7136\u65b0\u7684<\/span>j值\u8981\u5c0f\u4e8e\u4e4b\u524d\u7684<\/span>j值\uff0c\u6a21\u5f0f\u4e32\u624d\u4f1a\u662f\u53f3\u79fb\u7684\u6548\u679c\uff0c\u4e5f\u5c31\u662f\u8bf4\u5e94\u8be5\u6709<\/span>next[j]
      \n <= j -1\u3002\u90a3\u65b0\u7684<\/span>j值\u4e5f\u5c31\u662f<\/span>next[j]\u5e94\u8be5\u662f\u591a\u5c11\u5462\uff1f\u6211\u4eec\u89c2\u5bdf\u5982\u4e0b\u7684\u5339\u914d\uff1a<\/span><\/p>\n

            1)\u5982\u679c<\/span>\u6a21\u5f0f\u4e32\u53f3\u79fb1\u4f4d\uff08\u4ece\u7b80\u5355\u7684\u601d\u8003\u8d77\uff0c\u79fb\u52a8\u4e00\u4f4d\u4f1a\u600e\u4e48\u6837\uff09<\/span>\uff0c\u5373next[j] = j - 1\uff0c \u5373\u8ba9\u84dd\u8272\u7684<\/span>Si\u548c<\/span>Tj-1\u5339\u914d<\/span>(\u6ce8\uff1a\u7701\u7565\u53f7\u4e3a\u672a\u5339\u914d\u90e8\u5206<\/span>)<\/p>\n

                     S0,S1,S2,...,Si-j,Si-j+1...............,Si-1<\/span>, Si<\/span>, Si+1,....,Sn<\/p>\n

                                         T0,T1,.....................,Tj-1<\/span>, Tj<\/span>, .......... (T\u7684\u5212\u7ebf\u90e8\u5206\u548cS\u5212\u7ebf\u90e8\u5206\u76f8\u7b49\u30101\u3011)<\/p>\n

                                              T0,T1,.................Tj-2<\/span>,Tj-1<\/span>, ....... (\u79fb\u52a8\u540e\u7684T\u7684\u5212\u7ebf\u90e8\u5206\u548cS\u7684\u5212\u7ebf\u90e8\u5206\u76f8\u7b49\u30102\u3011)<\/p>\n

              \u6839\u636e\u30101\u3011\u3010<\/span>2\u3011\u53ef\u4ee5\u77e5\u9053\u5f53<\/span>next[j] =j -1\uff0c\u5373\u6a21\u5f0f\u4e32\u53f3\u79fb\u4e00\u4f4d\u7684\u65f6\u5019\uff0c\u6709<\/span>T[0 ~ j-2] == T[1 ~ j-1]\uff0c\u800c\u8fd9\u4e24\u90e8\u5206\u6070\u597d\u662f\u5b57\u7b26\u4e32<\/span>T[0 ~j-1]\u7684\u524d\u7f00\u548c\u540e\u7f00<\/span>\uff0c\u4e5f\u5c31\u662f\u8bf4<\/span>next[j]\u7684值\u53d6\u51b3\u4e8e\u6a21\u5f0f\u4e32<\/span>T\u4e2d<\/span>j\u524d\u9762\u90e8\u5206\u7684\u524d\u7f00\u548c\u540e\u7f00\u76f8\u7b49\u90e8\u5206\u7684\u957f\u5ea6\uff08\u597d\u597d\u63e3\u6469\u8fd9\u4e24\u4e2a\u5173\u952e\u5b57\u6982\u5ff5\uff1a\u524d\u7f00\u3001\u540e\u7f00\uff0c\u6216\u8005\u518d\u60f3\u60f3\uff0c\u6211\u7684\u4e0a\u4e00\u7bc7\u6587\u7ae0\uff0c\u4ece<\/span>Trie\u6811\u8c08\u5230\u540e\u7f00\u6811\u4e2d\uff0c\u540e\u7f00\u6811\u7684\u6982\u5ff5\uff09\u3002<\/span><\/p>\n<\/div>\n

      \n      2)\u5982\u679c\u6a21\u5f0f\u4e32\u53f3\u79fb<\/span>2\u4f4d\uff0c\u5373<\/span>next[j] = j - 2\uff0c \u5373\u8ba9\u84dd\u8272\u7684<\/span>Si\u548c<\/span>Tj-2\u5339\u914d    <\/span><\/p>\n

      \n               S0,S1,...,Si-j,Si-j+1,Si-j+2...............,Si-1<\/span>, Si<\/span>, Si+1,....,Sn<\/p>\n

      \n                                   T0,T1,T2,.....................,Tj-1<\/span>, Tj<\/span>, ..........(T\u7684\u5212\u7ebf\u90e8\u5206\u548cS\u5212\u7ebf\u90e8\u5206\u76f8\u7b49\u30103\u3011)<\/p>\n

      \n                                              T0,T1,...............,Tj-3<\/span>,Tj-2<\/span>,.........(\u79fb\u52a8\u540e\u7684T\u7684\u5212\u7ebf\u90e8\u5206\u548cS\u7684\u5212\u7ebf\u90e8\u5206\u76f8\u7b49\u30104\u3011)<\/p>\n

      \n        \u540c\u6837\u6839\u636e\u30103\u3011\u3010<\/span>4\u3011\u53ef\u4ee5\u77e5\u9053\u5f53<\/span>next[j] =j -2\uff0c\u5373\u6a21\u5f0f\u4e32\u53f3\u79fb\u4e24\u4f4d\u7684\u65f6\u5019\uff0c\u6709<\/span>T[0 ~ j-3] == T[2 ~ j-1]\u3002\u800c\u8fd9\u4e24\u90e8\u5206\u4e5f\u6070\u597d\u662f\u5b57\u7b26\u4e32<\/span>T[0 ~j-1]\u7684\u524d\u7f00\u548c\u540e\u7f00\uff0c\u4e5f\u5c31\u662f\u8bf4<\/span>next[j]\u7684值\u53d6\u51b3\u4e8e\u6a21\u5f0f\u4e32<\/span>T\u4e2d<\/span>j\u524d\u9762\u90e8\u5206\u7684\u524d\u7f00\u548c\u540e\u7f00\u76f8\u7b49\u90e8\u5206\u7684\u957f\u5ea6<\/span>\u3002<\/p>\n

      \n     3)\u4f9d\u6b21\u7c7b\u63a8\uff0c\u53ef\u4ee5\u5f97\u5230\u5982\u4e0b\u7ed3\u8bba\uff1a<\/span>\u5f53\u53d1\u751f\u5931\u914d\u7684\u60c5\u51b5\u4e0b\uff0cj\u7684\u65b0值<\/span>next[j]\u53d6\u51b3\u4e8e\u6a21\u5f0f\u4e32\u4e2d<\/span>T[0 ~ j-1]\u4e2d\u524d\u7f00\u548c\u540e\u7f00\u76f8\u7b49\u90e8\u5206\u7684\u957f\u5ea6\uff0c \u5e76\u4e14<\/span>next[j]\u6070\u597d\u7b49\u4e8e\u8fd9\u4e2a\u6700\u5927\u957f\u5ea6<\/span><\/strong>\u3002<\/p>\n

      \n    \u4e3a\u6b64\uff0c\u8bf7\u518d\u5141\u8bb8\u6211\u5f15\u7528\u4e0a\u6587\u4e2d\u7684\u4e00\u6bb5\u539f\u6587\uff1a\u201c<\/span>KMP\u7b97\u6cd5\u4e2d\uff0c\u5982\u679c\u5f53\u524d\u5b57\u7b26\u5339\u914d\u6210\u529f\uff0c\u5373<\/span>S[i]==T[j]\uff0c\u4ee4<\/span>i++\uff0c<\/span>j++\uff0c\u7ee7\u7eed\u5339\u914d\u4e0b\u4e00\u4e2a\u5b57\u7b26\uff1b\u5982\u679c<\/span>\u5339\u914d\u5931\u8d25\uff0c\u5373S[i]
      \n != T[j]\uff0c\u9700\u8981\u4fdd\u6301<\/span>i\u4e0d\u53d8\uff0c\u5e76\u4e14\u8ba9<\/span>j = next[j]\uff0c\u8fd9\u91cc<\/span>next[j] <=j -1\uff0c\u5373\u6a21\u5f0f\u4e32<\/span>T\u76f8\u5bf9\u4e8e\u539f\u59cb\u4e32<\/span>S\u5411\u53f3\u79fb\u52a8\u4e86\u81f3\u5c11<\/span>1\u4f4d<\/span>(\u79fb\u52a8\u7684\u5b9e\u9645\u4f4d\u6570<\/strong><\/span>j
      \n - next[j]  >=1<\/strong>),<\/p>\n

      \n    \u540c\u65f6\u79fb\u52a8\u4e4b\u540e\uff0ci\u4e4b\u524d\u7684\u90e8\u5206\uff08\u5373<\/span>S[i-j+1 ~ i-1]\uff09\uff0c\u548c<\/span>j=next[j]\u4e4b\u524d\u7684\u90e8\u5206\uff08\u5373<\/span>T[0 ~ j-2]<\/u>\uff09\u4ecd\u7136\u76f8\u7b49<\/u>\u3002\u663e\u7136\uff0c\u76f8\u5bf9\u4e8e<\/strong><\/span>BF\u7b97\u6cd5\u6765\u8bf4\uff0c<\/span>KMP<\/strong>\u79fb\u52a8\u66f4\u591a\u7684\u4f4d\u6570\uff0c\u8d77\u5230\u4e86\u4e00\u4e2a\u52a0\u901f\u7684\u4f5c\u7528<\/strong>\uff01 <\/span>(\u5931\u914d\u7684\u7279\u6b8a\u60c5\u5f62\uff0c\u4ee4<\/span>j=next[j]\u5bfc\u81f4<\/span>j==0\u7684\u65f6\u5019\uff0c\u9700\u8981\u5c06<\/span>i
      \n ++\uff0c\u5426\u5219\u6b64\u65f6\u6ca1\u6709\u79fb\u52a8\u6a21\u5f0f\u4e32)\u3002\u201d<\/span><\/p>\n

      \n    \u4e8e\u6b64\uff0c\u4e5f\u5c31\u4e0d\u96be\u7406\u89e3\u4e86\u6211\u7684\u5173\u4e8eKMP\u7b97\u6cd5\u7684\u7b2c\u4e8c\u7bc7\u6587\u7ae0\u4e4b\u4e2d\uff1a\u201c<\/span>\u5f53\u5339\u914d\u5230S[i] != P[j]\u7684\u65f6\u5019\u6709 S[i-j\u2026i-1] = P[0\u2026j-1]. \u5982\u679c\u4e0b\u9762\u7528j_next\u53bb\u5339\u914d\uff0c\u5219\u6709P[0\u2026j_next-1] = S[i-j_next\u2026i-1] = P[j-j_next\u2026j-1]\u3002\u6b64\u8fc7\u7a0b\u5982\u4e0b\u56fe3-1\u6240\u793a\u3002<\/p>\n

      \n  \u5f53\u5339\u914d\u5230<\/span>S[i] != P[j]<\/span>\u65f6\uff0cS[i-j\u2026i-1] = P[0\u2026j-1]<\/span>\uff1a<\/span><\/span><\/p>\n

      \nS: 0 \u2026 <\/span>i-j \u2026 i-1<\/u> i \u2026<\/span><\/span><\/p>\n

      \nP:       <\/span>0 \u2026   j-1<\/u> j \u2026<\/span><\/span><\/p>\n

      \n  \u5982\u679c\u4e0b\u9762\u7528j_next\u53bb\u5339\u914d\uff0c\u5219\u6709P[0\u2026j_next-1] = S[i-j_next\u2026i-1] = P[j-j_next\u2026j-1]\u3002
      \n\u6240\u4ee5\u5728P\u4e2d\u6709\u5982\u4e0b\u5339\u914d\u5173\u7cfb\uff08\u83b7\u5f97\u8fd9\u4e2a\u5339\u914d\u5173\u7cfb\u7684\u610f\u4e49\u662f\u7528\u6765\u6c42next\u6570\u7ec4\uff09<\/span><\/span><\/span>\uff1a<\/span><\/span><\/p>\n

      \nP: 0 \u2026 <\/span>j-j_next  .\u2026j-1_<\/u>    \u2026<\/span><\/span><\/p>\n

      \nP:        <\/span>0    \u2026 .j_next-1<\/u> \u2026<\/span><\/span><\/p>\n

      \n  \u6240\u4ee5\uff0c<\/span>\u6839\u636e\u4e0a\u9762\u4e24\u4e2a\u6b65\u9aa4\uff0c\u63a8\u51fa<\/span>\u4e0b\u4e00\u5339\u914d\u4f4d\u7f6e<\/span>j_next:<\/span><\/span><\/p>\n

      \nS: 0 \u2026 i-j \u2026 <\/span>i-j_next \u2026   i-1  <\/u>  <\/span>  <\/span>i \u2026<\/span><\/span><\/p>\n

      \nP:                   <\/span>0   \u2026 j_next-1<\/strong><\/u> <\/span><\/span>j_next \u2026<\/span><\/span><\/p>\n

      \n             \u56fe3-1 \u6c42j-next\uff08\u6700\u5927\u7684值\uff09\u7684\u4e09\u4e2a\u6b65\u9aa4<\/span><\/p>\n

      \n    \u4e0b\u9762\uff0c\u6211\u4eec\u7528\u53d8\u91cfk\u6765\u4ee3\u8868\u6c42\u5f97\u7684j_next\u7684\u6700\u5927值<\/strong>\uff0c\u5373k\u8868\u793a\u8fd9S[i]\u3001P[j]\u4e0d\u5339\u914d\u65f6P\u4e2d\u4e0b\u4e00\u4e2a\u7528\u6765\u5339\u914d\u7684\u4f4d\u7f6e\uff0c\u4f7f\u5f97P[0\u2026k-1] = P[j-k\u2026j-1]<\/u>\uff0c\u800c\u6211\u4eec\u8981\u5c3d\u91cf\u627e\u5230\u8fd9\u4e2ak\u7684\u6700\u5927值\u3002\u201d\u3002<\/span><\/span><\/p>\n

      \n      \u6839\u636e\u4e0a\u6587\u7684\u30101\u3011\u4e0e\u30102\u3011\u7684\u5339\u914d\u60c5\u51b5\uff0c\u53ef\u5f97\u7b2c\u4e8c\u7bc7\u6587\u7ae0\u4e4b\u4e2d\u6240\u8c13\u7684k=1\uff08\u5982aaaa\u7684\u5f62\u5f0f\uff09\uff0c\u6839\u636e\u4e0a\u6587\u7684\u30103\u3011\u4e0e\u30104\u3011\u7684\u5339\u914d\u60c5\u51b5\uff0ck=2\uff08\u5982abab\u7684\u5f62\u5f0f\uff09\u3002<\/p>\n

      \n     \u6240\u4ee5\uff0c\u5f52\u6839\u7a76\u5e95\uff0cKMP\u7b97\u6cd5\u7684\u672c\u8d28<\/span>\u4fbf\u662f\uff1a\u9488\u5bf9\u5f85\u5339\u914d\u7684\u6a21\u5f0f\u4e32\u7684\u7279\u70b9\uff0c\u5224\u65ad\u5b83\u662f\u5426\u6709\u91cd\u590d\u7684\u5b57\u7b26\uff0c\u4ece\u800c\u627e\u5230\u5b83\u7684\u524d\u7f00\u4e0e\u540e\u7f00\uff0c\u8fdb\u800c\u6c42\u51fa\u76f8\u5e94\u7684Next\u6570\u7ec4\uff0c\u6700\u7ec8\u6839\u636eNext\u6570\u7ec4\u800c\u8fdb\u884cKMP\u5339\u914d\u3002\u63a5\u4e0b\u6765\uff0c\u8fdb\u5165\u672c\u6587\u7684\u7b2c\u4e8c\u90e8\u5206\u3002<\/p>\n

      \n<\/a>\u7b2c\u4e8c\u90e8\u5206\u3001next\u6570\u7ec4\u6c42\u6cd5\u7684\u6765\u9f99\u53bb\u8109\u4e0e<\/span>KMP\u7b97\u6cd5\u7684\u6e90\u7801<\/span><\/h3>\n

      \n    \u672c\u90e8\u5206\u5f15\u81ea\u4e2a\u4eba\u6b64\u524d\u7684\u5173\u4e8eKMP\u7b97\u6cd5\u7684\u7b2c\u4e8c\u7bc7\u6587\u7ae0\uff1a\u516d\u4e4b\u7eed\u3001\u7531KMP\u7b97\u6cd5\u8c08\u5230BM\u7b97\u6cd5\u3002\u524d\u9762\uff0c\u6211\u4eec\u5df2\u7ecf\u77e5\u9053\u5373\u4e0d\u80fd\u8ba9P[j]=P[next[j]]\u6210\u7acb\u6210\u7acb\u3002\u4e0d\u80fd\u518d\u51fa\u73b0\u4e0a\u9762\u90a3\u6837\u7684\u60c5\u51b5\u554a\uff01<\/span>\u5373\u4e0d\u80fd\u6709\u8fd9\u79cd\u60c5\u51b5\u51fa\u73b0\uff1aP[3]=b\uff0c\u800c\u7adf\u4e5f\u6709P[next[3]]=P[1]=b<\/span>\u3002<\/span><\/span><\/p>\n

      \n    \u6b63\u5982\u5728\u7b2c\u4e8c\u7bc7\u6587\u7ae0\u4e2d\uff0c\u6240\u63d0\u5230\u7684\u90a3\u6837\uff1a\u201c\u8fd9\u91cc\u8bfb\u8005\u7406\u89e3\u53ef\u80fd\u6709\u56f0\u96be\u7684\u662f\u56e0\u4e3a\u6587\u4e2d\uff0c\u65f6\u800cnext\uff0c\u65f6\u800cnextval\uff0c\u628a\u4ed6\u4eec\u7684\u601d\u7ef4\u641e\u6df7\u4e71\u4e86\u3002\u5176\u5b9enext\u7528\u4e8e\u8868\u8fbe\u6570\u7ec4\u7d22\u5f15\uff0c\u800cnextval\u4e13\u7528\u4e8e\u8868\u8fbenext\u6570\u7ec4\u7d22\u5f15\u4e0b\u7684\u5177\u4f53\u5404值\uff0c\u533a\u522b\u7ec6\u5fae\u3002\u81f3\u4e8e\u6587\u4e2d\u8bf4\u4e0d\u5141\u8bb8P\"[j]\"=P[next[j]
      \n ]\u51fa\u73b0\uff0c\u662f\u56e0\u4e3a\u5df2\u7ecf\u6709P\"[3]\"=b\u4e0eS\"[i]\"\u5339\u914d\u8d25\uff0c\u800cP[next\"[3]\"]=P1=b\uff0c\u82e5\u518d\u62ffP[1]=b\u53bb\u4e0eS\"[i]\"\u5339\u914d\u5219\u5fc5\u8d25\u3002\u201d--\u516d\u4e4b\u7eed\u3001\u7531KMP\u7b97\u6cd5\u8c08\u5230BM\u7b97\u6cd5\u3002<\/span><\/span><\/span><\/p>\n

      \n   \u53c8\u6070\u6070\u5982\u4e0a\u6587\u4e2d\u6240\u8ff0\uff1a\u201c\u6a21\u5f0f\u4e32T<\/span>\u76f8\u5bf9\u4e8e\u539f\u59cb\u4e32S<\/span>\u5411\u53f3\u79fb\u52a8\u4e86\u81f3\u5c111<\/span>\u4f4d(<\/span>\u79fb\u52a8\u7684\u5b9e\u9645\u4f4d\u6570<\/strong>j
      \n - next[j]  >=1<\/span>)<\/span>\u201d<\/span><\/span>\u3002<\/span><\/span><\/span><\/span><\/p>\n

      \n    ok\uff0c\u6c42<\/span>next\u6570\u7ec4\u7684<\/span>get_nextval\u51fd\u6570\u6b63\u786e\u4ee3\u7801\u5982\u4e0b\uff1a<\/span><\/p>\n

      \n
      \n
      \n
      \nview plain<\/a><\/div>\n<\/div>\n
        \n
      1. \n\/\/\u4ee3\u78014-1  <\/span>  <\/span><\/span><\/li>\n
      2. \n\/\/\u4fee\u6b63\u540e\u7684\u6c42next\u6570\u7ec4\u5404值\u7684\u51fd\u6570\u4ee3\u7801  <\/span>  <\/span><\/span><\/li>\n
      3. \nvoid<\/span> get_nextval(<\/span>char<\/span> <\/span>const<\/span>* ptrn, <\/span>int<\/span> plen, <\/span>int<\/span>* nextval)    <\/span><\/span><\/li>\n
      4. \n{    <\/span><\/li>\n
      5. \n    int<\/span> i = 0;     <\/span><\/span><\/li>\n
      6. \n    nextval[i] = -1;    <\/span><\/li>\n
      7. \n    int<\/span> j = -1;    <\/span><\/span><\/li>\n
      8. \n    while<\/span>( i < plen-1 )    <\/span><\/span><\/li>\n
      9. \n    {    <\/span><\/li>\n
      10. \n        if<\/span>( j == -1 || ptrn[i] == ptrn[j] )   <\/span>\/\/\u5faa\u73af\u7684if\u90e8\u5206  <\/span>  <\/span><\/span><\/li>\n
      11. \n        {    <\/span><\/li>\n
      12. \n            ++i;    <\/span><\/li>\n
      13. \n            ++j;    <\/span><\/li>\n
      14. \n            \/\/\u4fee\u6b63\u7684\u5730\u65b9\u5c31\u53d1\u751f\u4e0b\u9762\u8fd94\u884c  <\/span>  <\/span><\/span><\/li>\n
      15. \n            if<\/span>( ptrn[i] != ptrn[j] ) <\/span>\/\/++i\uff0c++j\u4e4b\u540e\uff0c\u518d\u6b21\u5224\u65adptrn[i]\u4e0eptrn[j]\u7684\u5173\u7cfb  <\/span>  <\/span><\/span><\/li>\n
      16. \n                nextval[i] = j;      \/\/\u4e4b\u524d\u7684\u9519\u8bef\u89e3\u6cd5\u5c31\u5728\u4e8e\u6574\u4e2a\u5224\u65ad\u53ea\u6709\u8fd9\u4e00\u53e5\u3002  <\/span>  <\/span><\/span><\/li>\n
      17. \n            else<\/span>    <\/span><\/span><\/li>\n
      18. \n                nextval[i] = nextval[j];    <\/span><\/li>\n
      19. \n        }    <\/span><\/li>\n
      20. \n        else<\/span>                                 <\/span>\/\/\u5faa\u73af\u7684else\u90e8\u5206  <\/span>  <\/span><\/span><\/li>\n
      21. \n            j = nextval[j];    <\/span><\/li>\n
      22. \n    }    <\/span><\/li>\n
      23. \n}    <\/span><\/li>\n<\/ol>\n<\/div>\n<\/div>\n
        \n

            \u4e3e\u4e2a\u4f8b\u5b50\uff0c\u4e3e\u4f8b\u8bf4\u660e\u4e0b\u4e0a\u8ff0\u6c42next\u6570\u7ec4\u7684\u65b9\u6cd5\u3002
        \nS a b a b a b c
        \nP a b a b c
        \nS[4] != P[4]
        \n    \u90a3\u4e48\u4e0b\u4e00\u4e2a\u548cS[4]\u5339\u914d\u7684\u4f4d\u7f6e\u662fk=2(\u4e5f\u5373P[next[4]])\u3002\u6b64\u5904\u7684k=2\u4e5f\u518d\u6b21\u4f50\u8bc1\u4e86\u4e0a\u6587\u7b2c3\u8282\u5f00\u5934\u5904\u5173\u4e8e\u4e3a\u4e86\u627e\u5230\u4e0b\u4e00\u4e2a\u5339\u914d\u7684\u4f4d\u7f6e\u65f6k\u7684\u6c42\u6cd5\u3002\u4e0a\u9762\u7684\u4e3b\u4e32\u4e0e\u6a21\u5f0f\u4e32\u5f00\u59344\u4e2a\u5b57\u7b26\u90fd\u662f\u201cabab\u201d\uff0c\u6240\u4ee5\uff0c\u5339\u914d\u5931\u6548\u540e\u4e0b\u4e00\u4e2a\u5339\u914d\u7684\u4f4d\u7f6e\u76f4\u63a5\u8df3\u4e24\u6b65\u7ee7\u7eed\u8fdb\u884c\u5339\u914d\u3002
        \nS a b a b a b c
        \nP      a b a b c
        \n\u5339\u914d\u6210\u529f<\/span><\/p>\n

        P\u7684next\u6570\u7ec4值\u5206\u522b\u4e3a-1 0 -1 0 2<\/span><\/p>\n

            next\u6570\u7ec4\u5404值\u600e\u4e48\u6c42\u51fa\u6765\u7684\u5462?\u5206\u4ee5\u4e0b\u4e94\u6b65\uff1a<\/span><\/p>\n

          \n
        1. \u521d\u59cb\u5316\uff1ai=0\uff0cj=-1\uff0cnextval[0] = -1<\/strong>\u3002\u7531\u4e8ej == -1\uff0c\u8fdb\u5165\u4e0a\u8ff0\u5faa\u73af\u7684if\u90e8\u5206\uff0c++i\u5f97i=1\uff0c++j\u5f97j=0\uff0c\u4e14ptrn[i] != ptrn[j]\uff08\u5373a\uff01=b\uff09\uff09\uff0c\u6240\u4ee5\u5f97\u5230\u7b2c\u4e8c\u4e2anext值\u5373nextval[1] = 0\uff1b<\/span>\uff1b<\/span><\/li>\n
        2. i=1\uff0cj=0\uff0c\u8fdb\u5165\u5faa\u73afesle\u90e8\u5206\uff0c<\/span>j=nextval[j]=nextval[0]=-1\uff1b<\/span><\/li>\n
        3. \u8fdb\u5165\u5faa\u73af\u7684if\u90e8\u5206\uff0c++i\uff0c++j\uff0ci=2\uff0cj=0\uff0c\u56e0\u4e3aptrn[i]=ptrn[j]=a,\u6240\u4ee5nextval[2]=nextval[0]=-1\uff1b<\/span><\/li>\n
        4. i=2, j=0, \u7531\u4e8eptrn[i]=ptrn[j],\u518d\u6b21\u8fdb\u5165\u5faa\u73afif\u90e8\u5206\uff0c\u6240\u4ee5++i=3\uff0c++j=1,\u56e0\u4e3aptrn[i]=ptrn[j]=b,\u6240\u4ee5nextval[3]=nextval[1]=0\uff1b<\/span><\/li>\n
        5. i=3,j=1,\u7531\u4e8eptrn[i]=ptrn[j]=b,\u6240\u4ee5++i=4\uff0c++j=2,\u9000\u51fa\u5faa\u73af\u3002<\/span><\/li>\n<\/ol>\n<\/blockquote>\n

          \n    \u8fd9\u6837\u4e0a\u4f8b\u4e2d\u6a21\u5f0f\u4e32\u7684next\u6570\u7ec4\u5404值\u6700\u7ec8\u5e94\u8be5\u4e3a:<\/p>\n

          \n\"\"<\/p>\n

          \n            \u56fe4-1 \u6b63\u786e\u7684next\u6570\u7ec4\u5404值
          \n<\/span>next\u6570\u7ec4\u6c42\u89e3\u7684\u5177\u4f53\u8fc7\u7a0b\u5982\u4e0b\uff1a
          \n<\/strong>    \u521d\u59cb\u5316\uff1anextval[0] = -1\uff0c\u6211\u4eec\u5f97\u5230\u7b2c\u4e00\u4e2anext值\u5373-1.<\/p>\n

          \n\"\"<\/p>\n

          \n            \u56fe4-2 \u521d\u59cb\u5316\u7b2c\u4e00\u4e2anext值\u5373-1<\/span><\/p>\n

          \n    i = 0\uff0cj = -1\uff0c\u7531\u4e8ej == -1\uff0c\u8fdb\u5165\u4e0a\u8ff0\u5faa\u73af\u7684if\u90e8\u5206\uff0c++i\u5f97i=1\uff0c++j\u5f97j=0\uff0c\u4e14ptrn[i] != ptrn[j]\uff08\u5373a\uff01=b\uff09\uff09\uff0c\u6240\u4ee5\u5f97\u5230\u7b2c\u4e8c\u4e2anext值\u5373nextval[1] = 0\uff1b<\/p>\n

          \n\"\"<\/p>\n

          \n           \u56fe4-3 \u7b2c\u4e8c\u4e2anext值0<\/span><\/p>\n

          \n   \u4e0a\u9762\u6211\u4eec\u5df2\u7ecf\u5f97\u5230\uff0ci= 1\uff0cj = 0\uff0c\u7531\u4e8e\u4e0d\u6ee1\u8db3\u6761\u4ef6j == -1 || ptrn[i] == ptrn[j]\uff0c\u6240\u4ee5\u8fdb\u5165\u5faa\u73af\u7684esle\u90e8\u5206\uff0c\u5f97j = nextval[j] = -1\uff1b\u6b64\u65f6\uff0c\u4ecd\u6ee1\u8db3\u5faa\u73af\u6761\u4ef6\uff0c\u7531\u4e8ei = 1\uff0cj = -1\uff0c\u56e0\u4e3aj == -1\uff0c\u518d\u6b21\u8fdb\u5165\u5faa\u73af\u7684if\u90e8\u5206\uff0c++i\u5f97i=2\uff0c++j\u5f97j=0\uff0c\u7531\u4e8eptrn[i] == ptrn[j]\uff08\u5373ptrn[2]=ptrn[0]\uff0c\u4e5f\u5c31\u662f\u8bf4\u7b2c1\u4e2a\u5143\u7d20\u548c\u7b2c\u4e09\u4e2a\u5143\u7d20\u90fd\u662fa\uff09\uff0c\u6240\u4ee5\u8fdb\u5165\u5faa\u73afif\u90e8\u5206\u5185\u5d4c\u7684else\u90e8\u5206\uff0c\u5f97\u5230nextval[2] = nextval[0]
          \n = -1\uff1b<\/p>\n

          \n\"\"<\/p>\n

          \n         \u56fe4-4 \u7b2c\u4e09\u4e2anext\u6570\u7ec4\u5143\u7d20值-1<\/span><\/p>\n

          \n    i = 2\uff0cj = 0\uff0c\u7531\u4e8eptrn[i] == ptrn[j]\uff0c\u8fdb\u5165if\u90e8\u5206\uff0c++i\u5f97i=3\uff0c++j\u5f97j=1\uff0c\u6240\u4ee5ptrn[i] == ptrn[j]\uff08ptrn[3]==ptrn[1]\uff0c\u4e5f\u5c31\u662f\u8bf4\u7b2c2\u4e2a\u5143\u7d20\u548c\u7b2c4\u4e2a\u5143\u7d20\u90fd\u662fb\uff09\uff0c\u6240\u4ee5\u8fdb\u5165\u5faa\u73afif\u90e8\u5206\u5185\u5d4c\u7684else\u90e8\u5206\uff0c\u5f97\u5230nextval[3] = nextval[1] = 0\uff1b<\/p>\n

          \n\"\"<\/p>\n

          \n         \u56fe4-5 \u7b2c\u56db\u4e2a\u6570\u7ec4\u5143\u7d20值0
          \n<\/span>    \u5982\u679c\u4f60\u8fd8\u662f\u6ca1\u6709\u5f04\u61c2\u4e0a\u8ff0\u8fc7\u7a0b\u662f\u600e\u4e48\u4e00\u56de\u4e8b\uff0c\u8bf7\u73b0\u5728\u62ff\u51fa\u4e00\u5f20\u7eb8\u548c\u4e00\u652f\u7b14\u51fa\u6765\uff0c\u4e00\u6b65\u4e00\u6b65\u7684\u753b\u4e0b\u4e0a\u8ff0\u8fc7\u7a0b\u3002\u76f8\u4fe1\u6211\uff0c\u628a\u56fe\u753b\u51fa\u6765\u4e86\u4e4b\u540e\uff0c\u4f60\u4e00\u5b9a\u80fd\u660e\u767d\u5b83\u7684\u3002
          \n    \u7136\u540e\uff0c\u6211\u7559\u4e00\u4e2a\u95ee\u9898\u7ed9\u8bfb\u8005\uff0c\u4e3a\u4ec0\u4e48\u4e0a\u8ff0\u7684next\u6570\u7ec4\u8981\u90a3\u4e48\u6c42?\u6709\u4ec0\u4e48\u539f\u7406\u4e48?<\/p>\n

          \n    \u63d0\u793a<\/span>\uff1a\u6211\u4eec\u4ece\u4e0a\u8ff0\u5b57\u7b26\u4e32abab \u5404\u5b57\u7b26\u7684next值-1 0 -1 0<\/u>\uff0c\u53ef\u4ee5\u770b\u51fa\u6765\uff0c\u6839\u636e\u6c42\u5f97\u7684next\u6570\u7ec4值\uff0c\u5077\u7528\u524d\u7f00\u3001\u540e\u7f00\u7684\u6982\u5ff5\uff0c\u4e00\u5b9a\u53ef\u4ee5\u5224\u65ad\u51fa\u5728abab\u4e4b\u4e2d\uff0c\u524d\u7f00\u548c\u540e\u7f00\u76f8\u540c\uff0c\u5373\u90fd\u662fab\uff0c\u53cd\u8fc7\u6765\uff0c\u5982\u679c\u4e00\u4e2a\u5b57\u7b26\u4e32\u7684\u524d\u7f00\u548c\u540e\u7f00\u76f8\u540c\uff0c\u90a3\u4e48\u6839\u636e\u524d\u7f00\u548c\u540e\u7f00\u4f9d\u6b21\u6c42\u5f97\u7684next\u5404值\u4e5f\u662f\u76f8\u540c\u7684\u3002<\/p>\n

          \n