Sakuya滴刷题日记第一篇之KMP算法（LeetCode第28题）

第一篇之KMP算法（LeetCode第28题）"/>

Sakuya滴刷题日记第一篇之KMP算法（LeetCode第28题）

1.KMP算法

28. 找出字符串中第一个匹配项的下标

可在力扣中实践：

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

KMP算法本身不多做叙述，以下是在基本了解如何操作之后撰写的算法复习切入点。

（1）KMP算法更加聪明地回退

        暴力算法的匹配方式是一旦匹配失败，haystack的字符串的指针从i移至i+1，然后用needle重新匹配。而KMP遇到匹配失败，是将needle的指针前移，直到needle的指针所指的前一部分内容能够与目前haystack字符串的指针的前部分内容相等，而非直接将needle指针从0开始。

（2）next数组的定义

        next数组的定义：next[i]表示从needle[0]到needle[i]的这个子串里，正好满足前k个值与后k个值相等的最大的k，k不能取i+1（此时自己等于自己）。

        例如：如果needle字符串正好为abcabd。

        那么对于next[3]，也就是abca这个子串，此时k最大取1，即该子串的第一个以及最后一个相等，都为a，对于next[4]，也就是abcab这个子串，此时k最大取2，即该子串的前两个以及最后两个子串相等，都为ab。

（3）快速构建next数组

        首先，我们通过递推的方法来求解next数组，假设next数组的第0、1......n-1的值都已知，来推断next[n]的值。

        令next[n-1]的值为past，即从needle[0]到needle[n-1]组成的子串的前past与后past的值相同。

        第一步（恰好相等）：那么如果needle[n]的值恰好等于needle[past]呢，next[n]的值是否应该就是为past+1，即needle[0]到needle[n]组成的子串的前past+1的子串与后past+1的子串相等。同时，这也是唯二的next的产出方式之一（past为0为另一产出方式）。

        第二步（不等）：如果needle[n]的值与needle[past]不相等，那么我们能够知道，此时past太大了，我们需要找到一个（尽量大）小一点的前后相同字符串，即前past个元素组成的子串的前k个的前缀与后past个元素组成的子串的后k个的前缀正好相同。我们知道此时前past与后past因为正好是next[n-1]的结果，所以正好相等，所以我们的目标即转化为了：求前past个元素组成的子串的满足前k个值与后k个值相等的最大的k。也就是next[past-1]的定义。

        此时past，已经修改，我们拿回第一步，判断needle[n]是否与needle[past]相等。如果不等，持续按第二步方法缩小。直到为0。

（4）LeetCode第28题第二次实现代码

算法的学习过程不是一蹴而就的，多多练习，反复巩固！

class Solution {public int strStr(String haystack, String needle) {int[] next=new int[needle.length()];findNext(needle,next);int i=0;int k=0;while(i<haystack.length()&&k<needle.length()){if(haystack.charAt(i)==needle.charAt(k)){i++;k++;}else if(k==0){i++;}else{k=next[k-1];//对应讲解中更加聪明地回退 而非直接k=0}}if(k==needle.length()){return i-k;}else{return -1;}}public void findNext(String needle,int[] next){next[0]=0;for(int i=1;i<next.length;++i){int past=next[i-1];while(true){if(needle.charAt(i)==needle.charAt(past)){past++;break;//对应讲解中唯二的产出方式}else if(past==0){break;//对应讲解中唯二的产出方式}else{past=next[past-1];}}next[i]=past;}}
}