樸素的字串匹配演算法的時間復雜度為O(m*n)，m、n分別為主串、模式串的長度，容易理解的是，主串和模式串的指標同步進行，當遇到不匹配的字符時，主串指標將移動到當前指標下一位，因此最壞情況下m個字符都要匹配n次，而KMP演算法能在O(m + n)的時間復雜度內完成查找，原理不再介紹，下面介紹實作程序，
（1）首先在主串與模式串前均添加任一字符，使檢索時索引從1開始，
（2）預處理計算出next陣列以免后來匹配時重復計算，next陣列的作用即當出現主串、模式串不匹配的情況時，模式串指標需要從當前位置j跳轉到next[j]的位置重新進行匹配，計算next陣列的時間復雜度為O(n)，n為模式串長度，設i為計算next[i]的主索引，默認next[1] = 0直接跳過，令j = 0，i = 2，開始i++回圈，若p[i] = p[j + 1]，則j向右一位，next[i] = j；若p[i] != p[j + 1]，此時跳轉j = next[j]，直到j = 0或p[i] = p[j + 1]時停止跳轉，若此時p[i] = p[j + 1]，重復上一動作，next[i] = j，
int[] next = new int[n + 1]; for(int i = 2, j = 0; i <= n; i++){ while(j > 0 && p[i] != p[j + 1]) j = next[j]; if(p[i] == p[j + 1) j++; next[i] = j; }
（3）計算得到next陣列后進行模式匹配，設i為主串索引，j為模式串索引，令i = 1，j = 0，同樣，如果匹配失敗，則令模式串指標j跳回到next[j]處重新進行匹配，直到匹配成功時，j指標才后移，當j指標到達模式串末尾，說明匹配成功，回傳true，
for(int i = 1, j = 0; i <= m; i++){ while(j > 0 && s[i] != p[j + 1]) j = next[j]; if(s[i] == p[j + 1]) j++; if(j == n) return true; }
題目見Leetcode 28. 實作strStr()，鏈接：https://leetcode-cn.com/problems/implement-strstr/，
實作思路：【宮水三葉】簡單題學KMP演算法，鏈接：https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/464985.html
標籤：Java
上一篇：java學習之爬蟲
下一篇：惰性初始化