{"id":511,"date":"2022-04-15T15:35:54","date_gmt":"2022-04-15T07:35:54","guid":{"rendered":"http:\/\/120.55.184.7\/?p=511"},"modified":"2025-04-27T17:53:21","modified_gmt":"2025-04-27T09:53:21","slug":"kmp%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/beijian99.top\/?p=511","title":{"rendered":"KMP\u7b97\u6cd5"},"content":{"rendered":"\n

KMP \u7b97\u6cd5\u8be6\u89e3<\/p>\n\n\n\n

KMP\uff08Knuth-Morris-Pratt\uff09\u7b97\u6cd5\u662f\u4e00\u79cd\u9ad8\u6548\u7684\u5b57\u7b26\u4e32\u5339\u914d\u7b97\u6cd5\uff0c\u7528\u4e8e\u5728\u4e00\u4e2a\u4e3b\u4e32\uff08\u6587\u672c\u4e32\uff09\u4e2d\u67e5\u627e\u4e00\u4e2a\u6a21\u5f0f\u4e32\u7684\u51fa\u73b0\u4f4d\u7f6e\u3002\u4e0e\u66b4\u529b\u5339\u914d\u7b97\u6cd5\u76f8\u6bd4\uff0cKMP \u7b97\u6cd5\u901a\u8fc7\u9884\u5904\u7406\u6a21\u5f0f\u4e32\uff0c\u5229\u7528\u90e8\u5206\u5339\u914d\u4fe1\u606f\u907f\u514d\u4e86\u4e0d\u5fc5\u8981\u7684\u56de\u6eaf\uff0c\u4ece\u800c\u5c06\u65f6\u95f4\u590d\u6742\u5ea6\u4f18\u5316\u5230 O(n + m)\uff0c\u5176\u4e2d n \u662f\u4e3b\u4e32\u7684\u957f\u5ea6\uff0cm \u662f\u6a21\u5f0f\u4e32\u7684\u957f\u5ea6\u3002<\/p>\n\n\n\n

\n\n\n\n

\u4e00\u3001\u66b4\u529b\u5339\u914d\u7b97\u6cd5\u7684\u95ee\u9898<\/p>\n\n\n\n

\u5728\u66b4\u529b\u5339\u914d\u7b97\u6cd5\u4e2d\uff0c\u6211\u4eec\u4ece\u4e3b\u4e32\u7684\u7b2c\u4e00\u4e2a\u5b57\u7b26\u5f00\u59cb\uff0c\u9010\u4e2a\u5b57\u7b26\u4e0e\u6a21\u5f0f\u4e32\u8fdb\u884c\u6bd4\u8f83\u3002\u5982\u679c\u53d1\u73b0\u4e0d\u5339\u914d\uff0c\u5219\u5c06\u4e3b\u4e32\u7684\u6307\u9488\u56de\u6eaf\u5230\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\uff0c\u6a21\u5f0f\u4e32\u7684\u6307\u9488\u91cd\u65b0\u56de\u5230\u8d77\u59cb\u4f4d\u7f6e\u3002\u8fd9\u79cd\u56de\u6eaf\u4f1a\u5bfc\u81f4\u5927\u91cf\u7684\u91cd\u590d\u6bd4\u8f83\uff0c\u6548\u7387\u8f83\u4f4e\u3002<\/p>\n\n\n\n

\u793a\u4f8b\uff1a
\u4e3b\u4e32\uff1aABABDABACDABABCABAB<\/code>
\u6a21\u5f0f\u4e32\uff1aABABCABAB<\/code><\/p>\n\n\n\n

\u5728\u66b4\u529b\u5339\u914d\u4e2d\uff0c\u5f53\u6bd4\u8f83\u5230\u4e3b\u4e32\u7684\u7b2c 9 \u4e2a\u5b57\u7b26 C<\/code> \u548c\u6a21\u5f0f\u4e32\u7684\u7b2c 4 \u4e2a\u5b57\u7b26 C<\/code> \u65f6\uff0c\u53d1\u73b0\u4e0d\u5339\u914d\u3002\u6b64\u65f6\uff0c\u4e3b\u4e32\u7684\u6307\u9488\u56de\u6eaf\u5230\u7b2c 2 \u4e2a\u5b57\u7b26\uff0c\u6a21\u5f0f\u4e32\u7684\u6307\u9488\u56de\u6eaf\u5230\u7b2c 1 \u4e2a\u5b57\u7b26\uff0c\u91cd\u65b0\u5f00\u59cb\u6bd4\u8f83\u3002\u8fd9\u79cd\u56de\u6eaf\u662f\u5197\u4f59\u7684\uff0c\u56e0\u4e3a\u6a21\u5f0f\u4e32\u7684\u524d\u51e0\u4e2a\u5b57\u7b26\u5df2\u7ecf\u4e0e\u4e3b\u4e32\u7684\u67d0\u4e9b\u90e8\u5206\u5339\u914d\u3002<\/p>\n\n\n\n

\n\n\n\n

\u4e8c\u3001KMP \u7b97\u6cd5\u7684\u6838\u5fc3\u601d\u60f3<\/p>\n\n\n\n

KMP \u7b97\u6cd5\u7684\u6838\u5fc3\u601d\u60f3\u662f\u5229\u7528\u6a21\u5f0f\u4e32\u672c\u8eab\u7684\u4fe1\u606f\uff0c\u5728\u5339\u914d\u5931\u8d25\u65f6\uff0c\u907f\u514d\u4e3b\u4e32\u6307\u9488\u7684\u56de\u6eaf\uff0c\u800c\u662f\u901a\u8fc7\u9884\u5904\u7406\u6a21\u5f0f\u4e32\u5f97\u5230\u7684\u201c\u90e8\u5206\u5339\u914d\u8868\u201d\uff08\u4e5f\u79f0\u4e3a\u201c\u5931\u8d25\u51fd\u6570\u201d\u6216\u201cnext \u6570\u7ec4\u201d\uff09\uff0c\u51b3\u5b9a\u6a21\u5f0f\u4e32\u6307\u9488\u7684\u79fb\u52a8\u4f4d\u7f6e\u3002<\/p>\n\n\n\n

\u90e8\u5206\u5339\u914d\u8868\uff08next \u6570\u7ec4\uff09\u7684\u5b9a\u4e49\uff1a
\u5bf9\u4e8e\u6a21\u5f0f\u4e32 P<\/code>\uff0cnext[i]<\/code> \u8868\u793a P[0..i-1]<\/code> \u7684\u6700\u957f\u76f8\u540c\u524d\u7f00\u540e\u7f00\u7684\u957f\u5ea6\u3002\u5373\uff0cP[0..next[i]-1]<\/code> \u662f P[0..i-1]<\/code> \u7684\u6700\u957f\u76f8\u7b49\u524d\u7f00\u548c\u540e\u7f00\u3002<\/p>\n\n\n\n

\u793a\u4f8b\uff1a
\u6a21\u5f0f\u4e32 P = \"ABABCABAB\"<\/code> \u7684 next \u6570\u7ec4\u4e3a [0, 0, 1, 2, 0, 1, 2, 3, 4]<\/code>\u3002<\/p>\n\n\n\n

\n\n\n\n

\u4e09\u3001KMP \u7b97\u6cd5\u7684\u6b65\u9aa4<\/p>\n\n\n\n

    \n
  1. \u9884\u5904\u7406\u6a21\u5f0f\u4e32\uff0c\u6784\u5efa next \u6570\u7ec4<\/li>\n<\/ol>\n\n\n\n

    \u6211\u4eec\u9700\u8981\u4e3a\u6a21\u5f0f\u4e32 P<\/code> \u6784\u5efa\u4e00\u4e2a next<\/code> \u6570\u7ec4\uff0cnext[i]<\/code> \u8868\u793a P[0..i-1]<\/code> \u7684\u6700\u957f\u76f8\u540c\u524d\u7f00\u540e\u7f00\u7684\u957f\u5ea6\u3002<\/p>\n\n\n\n

    \u6784\u5efa next \u6570\u7ec4\u7684\u6b65\u9aa4\uff1a<\/p>\n\n\n\n

      \n
    • \u521d\u59cb\u5316 next[0] = 0<\/code>\uff0c\u56e0\u4e3a\u5355\u4e2a\u5b57\u7b26\u6ca1\u6709\u524d\u7f00\u548c\u540e\u7f00\u3002<\/li>\n\n\n\n
    • \u4f7f\u7528\u4e24\u4e2a\u6307\u9488 i<\/code> \u548c j<\/code>\uff0c\u5176\u4e2d i<\/code> \u8868\u793a\u5f53\u524d\u5b57\u7b26\u7684\u4f4d\u7f6e\uff0cj<\/code> \u8868\u793a\u5f53\u524d\u6700\u957f\u76f8\u540c\u524d\u7f00\u540e\u7f00\u7684\u957f\u5ea6\u3002<\/li>\n\n\n\n
    • \u5982\u679c P[i] == P[j]<\/code>\uff0c\u5219 next[i+1] = j + 1<\/code>\uff0c\u5e76\u79fb\u52a8 i<\/code> \u548c j<\/code>\u3002<\/li>\n\n\n\n
    • \u5982\u679c P[i] != P[j]<\/code>\uff0c\u5219 j<\/code> \u56de\u9000\u5230 next[j-1]<\/code>\uff0c\u76f4\u5230 P[i] == P[j]<\/code> \u6216 j == 0<\/code>\u3002<\/li>\n<\/ul>\n\n\n\n

      \u793a\u4f8b\uff1a
      \u6a21\u5f0f\u4e32 P = \"ABABCABAB\"<\/code> \u7684 next \u6570\u7ec4\u6784\u5efa\u8fc7\u7a0b\uff1a<\/p>\n\n\n\n

      i<\/th>P[i]<\/th>j<\/th>next[i+1]<\/th><\/tr><\/thead>
      0<\/td>‘A’<\/td>0<\/td>0<\/td><\/tr>
      1<\/td>‘B’<\/td>0<\/td>0<\/td><\/tr>
      2<\/td>‘A’<\/td>0<\/td>1 (P[0] == P[2])<\/td><\/tr>
      3<\/td>‘B’<\/td>1<\/td>2 (P[0..1] == P[2..3])<\/td><\/tr>
      4<\/td>‘C’<\/td>2<\/td>0 (P[2] != P[4])<\/td><\/tr>
      5<\/td>‘A’<\/td>0<\/td>1 (P[0] == P[5])<\/td><\/tr>
      6<\/td>‘B’<\/td>1<\/td>2 (P[0..1] == P[5..6])<\/td><\/tr>
      7<\/td>‘A’<\/td>2<\/td>3 (P[0..2] == P[5..7])<\/td><\/tr>
      8<\/td>‘B’<\/td>3<\/td>4 (P[0..3] == P[5..8])<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

      \u6700\u7ec8 next<\/code> \u6570\u7ec4\u4e3a [0, 0, 1, 2, 0, 1, 2, 3, 4]<\/code>\u3002<\/p>\n\n\n\n

      \n\n\n\n
        \n
      1. \u4f7f\u7528 next \u6570\u7ec4\u8fdb\u884c\u5339\u914d<\/li>\n<\/ol>\n\n\n\n

        \u5728\u4e3b\u4e32 S<\/code> \u548c\u6a21\u5f0f\u4e32 P<\/code> \u7684\u5339\u914d\u8fc7\u7a0b\u4e2d\uff0c\u5982\u679c\u53d1\u73b0\u4e0d\u5339\u914d\uff0c\u53ef\u4ee5\u6839\u636e next<\/code> \u6570\u7ec4\u79fb\u52a8\u6a21\u5f0f\u4e32\u7684\u6307\u9488\uff0c\u800c\u4e0d\u662f\u56de\u6eaf\u4e3b\u4e32\u7684\u6307\u9488\u3002<\/p>\n\n\n\n

        \u5339\u914d\u6b65\u9aa4\uff1a<\/p>\n\n\n\n

          \n
        • \u521d\u59cb\u5316\u4e3b\u4e32\u6307\u9488 i = 0<\/code>\uff0c\u6a21\u5f0f\u4e32\u6307\u9488 j = 0<\/code>\u3002<\/li>\n\n\n\n
        • \u5982\u679c S[i] == P[j]<\/code>\uff0c\u5219 i++<\/code>\uff0cj++<\/code>\u3002<\/li>\n\n\n\n
        • \u5982\u679c j == m<\/code>\uff08\u6a21\u5f0f\u4e32\u957f\u5ea6\uff09\uff0c\u5219\u5339\u914d\u6210\u529f\uff0c\u8fd4\u56de i - j<\/code>\u3002<\/li>\n\n\n\n
        • \u5982\u679c S[i] != P[j]<\/code>\uff1a \u2022 \u5982\u679c j > 0<\/code>\uff0c\u5219 j = next[j-1]<\/code>\u3002 \u2022 \u5982\u679c j == 0<\/code>\uff0c\u5219 i++<\/code>\u3002<\/li>\n\n\n\n
        • \u91cd\u590d\u4e0a\u8ff0\u6b65\u9aa4\uff0c\u76f4\u5230 i == n<\/code>\uff08\u4e3b\u4e32\u957f\u5ea6\uff09\u6216 j == m<\/code>\u3002<\/li>\n<\/ul>\n\n\n\n

          \u793a\u4f8b\uff1a
          \u4e3b\u4e32 S = \"ABABDABACDABABCABAB\"<\/code>\uff0c\u6a21\u5f0f\u4e32 P = \"ABABCABAB\"<\/code>\u3002<\/p>\n\n\n\n

          \u5339\u914d\u8fc7\u7a0b\uff1a<\/p>\n\n\n\n

            \n
          1. \u521d\u59cb i = 0<\/code>, j = 0<\/code>\u3002<\/li>\n\n\n\n
          2. \u9010\u4e2a\u5b57\u7b26\u6bd4\u8f83\uff0c\u76f4\u5230 i = 4<\/code>, j = 4<\/code> \u65f6 S[4] = 'D'<\/code> \u4e0d\u7b49\u4e8e P[4] = 'C'<\/code>\u3002<\/li>\n\n\n\n
          3. j = next[3] = 2<\/code>\uff0c\u7ee7\u7eed\u6bd4\u8f83 S[4]<\/code> \u548c P[2]<\/code>\u3002<\/li>\n\n\n\n
          4. \u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 0<\/code>\u3002<\/li>\n\n\n\n
          5. \u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          6. \u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          7. \u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          8. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          9. \u6700\u7ec8\u5728 i = 10<\/code>, j = 0<\/code> \u540e\uff0c\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          10. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          11. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          12. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          13. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          14. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          15. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          16. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          17. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          18. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          19. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n\n\n\n
          20. \u5b9e\u9645\u4e0a\uff0c\u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\u4f1a\u5728 i = 10<\/code>, j = 0<\/code> \u540e\u7ee7\u7eed\u6bd4\u8f83\uff0c\u76f4\u5230 i = 10<\/code>, j = 1<\/code> \u65f6 S[10] = 'A'<\/code> \u7b49\u4e8e P[1] = 'B'<\/code>\uff0c\u4e0d\u5339\u914d\uff0cj = next[0] = 0<\/code>\u3002<\/li>\n<\/ol>\n\n\n\n

            \uff08\u6ce8\uff1a\u4e0a\u8ff0\u6b65\u9aa4\u6709\u8bef\uff0c\u5b9e\u9645\u5339\u914d\u8fc7\u7a0b\u5982\u4e0b\uff09<\/p>\n\n\n\n

            \u6b63\u786e\u7684\u5339\u914d\u8fc7\u7a0b\uff1a<\/p>\n\n\n\n

              \n
            1. \u521d\u59cb i = 0<\/code>, j = 0<\/code>\u3002<\/li>\n\n\n\n
            2. \u6bd4\u8f83 S[0]<\/code> \u548c P[0]<\/code>\uff0c\u5339\u914d\uff0ci = 1<\/code>, j = 1<\/code>\u3002<\/li>\n\n\n\n
            3. \u6bd4\u8f83 S[1]<\/code> \u548c P[1]<\/code>\uff0c\u5339\u914d\uff0ci = 2<\/code>, j = 2<\/code>\u3002<\/li>\n\n\n\n
            4. \u6bd4\u8f83 S[2]<\/code> \u548c P[2]<\/code>\uff0c\u5339\u914d\uff0ci = 3<\/code>, j = 3<\/code>\u3002<\/li>\n\n\n\n
            5. \u6bd4\u8f83 S[3]<\/code> \u548c P[3]<\/code>\uff0c\u5339\u914d\uff0ci = 4<\/code>, j = 4<\/code>\u3002<\/li>\n\n\n\n
            6. \u6bd4\u8f83 S[4]<\/code> \u548c P[4]<\/code>\uff0c\u4e0d\u5339\u914d\uff08'D' != 'C'<\/code>\uff09\uff0cj = next[3] = 2<\/code>\u3002<\/li>\n\n\n\n
            7. \u6bd4\u8f83 S[4]<\/code> \u548c P[2]<\/code>\uff0c\u4e0d\u5339\u914d\uff08'D' != 'A'<\/code>\uff09\uff0cj = next[1] = 0<\/code>\u3002<\/li>\n\n\n\n
            8. \u6bd4\u8f83 S[4]<\/code> \u548c P[0]<\/code>\uff0c\u4e0d\u5339\u914d\uff08'D' != 'A'<\/code>\uff09\uff0ci = 5<\/code>, j = 0<\/code>\u3002<\/li>\n\n\n\n
            9. \u6bd4\u8f83 S[5]<\/code> \u548c P[0]<\/code>\uff0c\u5339\u914d\uff0ci = 6<\/code>, j = 1<\/code>\u3002<\/li>\n\n\n\n
            10. \u6bd4\u8f83 S[6]<\/code> \u548c P[1]<\/code>\uff0c\u5339\u914d\uff0ci = 7<\/code>, j = 2<\/code>\u3002<\/li>\n\n\n\n
            11. \u6bd4\u8f83 S[7]<\/code> \u548c P[2]<\/code>\uff0c\u5339\u914d\uff0ci = 8<\/code>, j = 3<\/code>\u3002<\/li>\n\n\n\n
            12. \u6bd4\u8f83 S[8]<\/code> \u548c P[3]<\/code>\uff0c\u5339\u914d\uff0ci = 9<\/code>, j = 4<\/code>\u3002<\/li>\n\n\n\n
            13. \u6bd4\u8f83 S[9]<\/code> \u548c P[4]<\/code>\uff0c\u4e0d\u5339\u914d\uff08'B' != 'C'<\/code>\uff09\uff0cj = next[3] = 2<\/code>\u3002<\/li>\n\n\n\n
            14. \u6bd4\u8f83 S[9]<\/code> \u548c P[2]<\/code>\uff0c\u4e0d\u5339\u914d\uff08'B' != 'A'<\/code>\uff09\uff0cj = next[1] = 0<\/code>\u3002<\/li>\n\n\n\n
            15. \u6bd4\u8f83 S[9]<\/code> \u548c P[0]<\/code>\uff0c\u4e0d\u5339\u914d\uff08'B' != 'A'<\/code>\uff09\uff0ci = 10<\/code>, j = 0<\/code>\u3002<\/li>\n\n\n\n
            16. \u6bd4\u8f83 S[10]<\/code> \u548c P[0]<\/code>\uff0c\u5339\u914d\uff0ci = 11<\/code>, j = 1<\/code>\u3002<\/li>\n\n\n\n
            17. \u6bd4\u8f83 S[11]<\/code> \u548c P[1]<\/code>\uff0c\u5339\u914d\uff0ci = 12<\/code>, j = 2<\/code>\u3002<\/li>\n\n\n\n
            18. \u6bd4\u8f83 S[12]<\/code> \u548c P[2]<\/code>\uff0c\u5339\u914d\uff0ci = 13<\/code>, j = 3<\/code>\u3002<\/li>\n\n\n\n
            19. \u6bd4\u8f83 S[13]<\/code> \u548c P[3]<\/code>\uff0c\u5339\u914d\uff0ci = 14<\/code>, j = 4<\/code>\u3002<\/li>\n\n\n\n
            20. \u6bd4\u8f83 S[14]<\/code> \u548c P[4]<\/code>\uff0c\u5339\u914d\uff0ci = 15<\/code>, j = 5<\/code>\u3002<\/li>\n\n\n\n
            21. \u6bd4\u8f83 S[15]<\/code> \u548c P[5]<\/code>\uff0c\u5339\u914d\uff0ci = 16<\/code>, j = 6<\/code>\u3002<\/li>\n\n\n\n
            22. \u6bd4\u8f83 S[16]<\/code> \u548c P[6]<\/code>\uff0c\u5339\u914d\uff0ci = 17<\/code>, j = 7<\/code>\u3002<\/li>\n\n\n\n
            23. \u6bd4\u8f83 S[17]<\/code> \u548c P[7]<\/code>\uff0c\u5339\u914d\uff0ci = 18<\/code>, j = 8<\/code>\u3002<\/li>\n\n\n\n
            24. j == m<\/code>\uff0c\u5339\u914d\u6210\u529f\uff0c\u8fd4\u56de i - j = 10<\/code>\u3002<\/li>\n<\/ol>\n\n\n\n
              \n\n\n\n

              \u56db\u3001KMP \u7b97\u6cd5\u7684\u5b9e\u73b0<\/p>\n\n\n\n

              \u4ee5\u4e0b\u662f KMP \u7b97\u6cd5\u7684 Python \u5b9e\u73b0\uff1a<\/p>\n\n\n

              \n#include <iostream>\n#include <vector>\n#include <string>\n\nusing namespace std;\n\n\/\/ \u8ba1\u7b97 next \u6570\u7ec4\nvector<int> compute_next(const string& pattern) {\n    int m = pattern.length();\n    vector<int> next(m, 0);\n    int j = 0;\n    for (int i = 1; i < m; ++i) {\n        while (j > 0 && pattern[i] != pattern[j]) {\n            j = next[j - 1];\n        }\n        if (pattern[i] == pattern[j]) {\n            ++j;\n        }\n        next[i] = j;\n    }\n    return next;\n}\n\n\/\/ KMP \u5b57\u7b26\u4e32\u5339\u914d\nint kmp_search(const string& text, const string& pattern) {\n    int n = text.length();\n    int m = pattern.length();\n    if (m == 0) {\n        return 0; \/\/ \u7a7a\u6a21\u5f0f\u4e32\u5339\u914d\u6210\u529f\uff0c\u8fd4\u56de 0\n    }\n    vector<int> next = compute_next(pattern);\n    int j = 0;\n    for (int i = 0; i < n; ++i) {\n        while (j > 0 && text[i] != pattern[j]) {\n            j = next[j - 1];\n        }\n        if (text[i] == pattern[j]) {\n            ++j;\n        }\n        if (j == m) {\n            return i - m + 1; \/\/ \u8fd4\u56de\u5339\u914d\u7684\u8d77\u59cb\u4f4d\u7f6e\n        }\n    }\n    return -1; \/\/ \u672a\u627e\u5230\u5339\u914d\n}\n\nint main() {\n    string text = "ABABDABACDABABCABAB";\n    string pattern = "ABABCABAB";\n    int pos = kmp_search(text, pattern);\n    if (pos != -1) {\n        cout << "Pattern found at index: " << pos << endl;\n    } else {\n        cout << "Pattern not found." << endl;\n    }\n    return 0;\n}\n<\/pre><\/div>\n\n\n
              \n\n\n\n
              \u4e94\u3001KMP \u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n\n\n\n
                \n
              • \u6784\u5efa next \u6570\u7ec4\uff1a\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(m)\uff0c\u5176\u4e2d m \u662f\u6a21\u5f0f\u4e32\u7684\u957f\u5ea6\u3002<\/li>\n\n\n\n
              • \u5339\u914d\u8fc7\u7a0b\uff1a\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(n)\uff0c\u5176\u4e2d n \u662f\u4e3b\u4e32\u7684\u957f\u5ea6\u3002<\/li>\n\n\n\n
              • \u603b\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n + m)\u3002<\/li>\n<\/ul>\n\n\n\n
                \n\n\n\n
                \n\n\n\n
                \u4e03\u3001\u603b\u7ed3<\/p>\n\n\n\n
                KMP \u7b97\u6cd5\u901a\u8fc7\u9884\u5904\u7406\u6a21\u5f0f\u4e32\uff0c\u5229\u7528\u90e8\u5206\u5339\u914d\u4fe1\u606f\u907f\u514d\u4e86\u4e3b\u4e32\u6307\u9488\u7684\u56de\u6eaf\uff0c\u4ece\u800c\u63d0\u9ad8\u4e86\u5b57\u7b26\u4e32\u5339\u914d\u7684\u6548\u7387\u3002\u5176\u6838\u5fc3\u5728\u4e8e\u6784\u5efa next \u6570\u7ec4\uff0c\u5e76\u5728\u5339\u914d\u8fc7\u7a0b\u4e2d\u5229\u7528\u8be5\u6570\u7ec4\u5feb\u901f\u79fb\u52a8\u6a21\u5f0f\u4e32\u7684\u6307\u9488\u3002KMP \u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(n)<\/p>\n","protected":false},"excerpt":{"rendered":"
                KMP \u7b97\u6cd5\u8be6\u89e3 KMP\uff08Knuth-Morris-Pratt\uff09\u7b97\u6cd5\u662f\u4e00\u79cd\u9ad8\u6548\u7684\u5b57\u7b26\u4e32\u5339\u914d\u7b97\u6cd5\uff0c\u7528\u4e8e\u5728\u4e00\u4e2a\u4e3b\u4e32 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[4],"tags":[123],"class_list":["post-511","post","type-post","status-publish","format-standard","hentry","category-algorithm","tag-123"],"_links":{"self":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/511","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=511"}],"version-history":[{"count":4,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/511\/revisions"}],"predecessor-version":[{"id":797,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/511\/revisions\/797"}],"wp:attachment":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=511"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=511"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=511"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}