[JAVA][算法] [字符串匹配]KMP

桃扇骨 2023-02-24 15:28 36阅读 0赞

### 我们为什么需要KMP？ ###

在**字符串匹配**问题中，我们需要找到匹配串pattern在原串text中的位置，一种显而易见的思路就是暴力匹配，如图所示，我们把pattern放置到text中的每个位置进行比较即可。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

但是大家可以发现，这种方式的时间复杂度太高了，达到了O(pattern.length \* text.length)，我们是否可以进一步进行优化呢？在第一次匹配时，abaa和abab的最后一个字符不匹配，前面aba都匹配好了，移动了一位之后，发现前面又匹配不上了，这次移动相当于多此一举。换句话说，**我们每次移动应当让前面仍然保持匹配状态，直接比较后面的位置。**

本例中应当直接移动两位，让aaab和abaa比较，这也就是KMP的基本思想了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

## 基础知识 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

## 求匹配数组maxMatchLens ##

那么我们如何做到在移动的过程中保证前面的匹配状态呢？下图可以清晰地描述：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
发生匹配错误的字符为c，左端为abab，在移动的时候，要保证真前缀和真后缀相等且长度最大（选了较小的会忽略可能正确的结果），对于abab：

> 真前缀：a ab aba  
> 真后缀：b ab bab

也就是说，我们需要找到pattern中所有位置，相匹配的真前缀与真后缀中，最长的字符串的长度，这也就是我们**经常听到的next数组了，这里我们用maxMatchLens来表示**，如下图所示的例子中，假设我们已经求出来前面所有的值了，最后一个值如何求解呢？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
**举例： 第五位 c**  
![在这里插入图片描述][20200709211212328.png]

<table> 
 <thead> 
  <tr> 
   <th>c各参数取值</th> 
   <th>Value c1</th> 
   <th>Value c2</th> 
   <th>Value c3</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>currentLen</td> 
   <td>2</td> 
   <td>1</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>pattern.charAt(currentLen)</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>4</td> 
   <td>4</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>pattern.charAt(i)</td> 
   <td>c</td> 
   <td>c</td> 
   <td>c</td> 
  </tr> 
  <tr> 
   <td>处理</td> 
   <td>1.while字符不相等</td> 
   <td>1.while字符不相等</td> 
   <td>3.赋值 <strong>maxMatchLens[4] = currentLen=0;</strong></td> 
  </tr> 
 </tbody> 
</table>

private int[] getMaxMatchLens(String pattern) { 
        int[] maxMatchLens = new int[pattern.length()];
        int currentLen = 0;
        for (int i = 1; i < pattern.length(); i++) { 
            while (currentLen > 0 && pattern.charAt(i) != pattern.charAt(currentLen)) { 
                currentLen = maxMatchLens[currentLen - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(currentLen)) { 
                currentLen++;
            }
            maxMatchLens[i] = currentLen;
        }
        return maxMatchLens;
    }

## KMP匹配 ##

**返回起始坐标 （text里面找pattern）**  
匹配的思路与求maxMatchLens的思路基本一致，即按照最长、次长的顺序进行移位匹配，代码如下：

private List<Integer> search(String text, String pattern) { 
        List<Integer> res = new ArrayList<>();
        int[] maxMatchLens = getMaxMatchLens(pattern);
        int j = 0;
        for (int i = 0; i < text.length(); i++) { 
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) { 
                j = maxMatchLens[j - 1];
            }
            if (pattern.charAt(j) == text.charAt(i)) { 
                j++;
            }
            if (j == pattern.length()) { 
                res.add(i - j + 1);
                j = maxMatchLens[j - 1];
            }
        }
        return res;
    }

参考链接：https://leetcode-cn.com/problems/longest-happy-prefix/solution/ni-zhen-de-li-jie-kmpma-jiao-ni-xun-su-zhang-wo-bi/  
参考链接：https://blog.csdn.net/V\_0617/article/details/79114860

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/faf70d07e6e84ac0a6853933e2a3f504.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230209/32b6b5f7fc4b4d568d7e834643819016.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20230209/c5fe1870ba504bed8ec71c199f2468b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20230209/4a04b5bcbdc44fda9c3ecbe71a675721.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: /images/20230209/b2a2ef255da44f8c95cdb46336864e61.png
[20200709211212328.png]: /images/20230209/3adffb026845470482f62878ff66b9f1.png