dede网站地图html/微营销平台

题目
KMP算法，如题目所示，主要解决快速匹配的问题。但是这个不是重点，这个算法主要是解决，在一次匹配不成功的情况下，如何快速找到下一个匹配点。

如何找到下一个匹配点？

当然是前面有几个字符相同，那我继续对比下一个位置的字符不就行了吗？

真的就是这么简单！

那前面有几个字符相同啊？每个位置不同，每个位置前面的字符都不一样啊！

那就必须记录下来了，所以我们必须会开一个数组来记录每个位置，后缀最长有几个字符跟前缀相同。这算是用空间去换时间了。

什么是后缀，什么是前缀？？

前缀：就是从左边开始，连续的子字符串，就是一个字符串的前缀。

后缀：就是从某处开始，直到最后的连续的子字符串，就是一个字符串的后缀。

我们没必要纠结为什么左边叫前，右边的叫后，这个没啥意义，习惯而已。

我们需要知道，一个字符串，它的前缀跟后缀如果相同的话，最长的长度是多少。

我们可以理解为，这个字符串的后面几位跟这个字符串的前面几位，一模一样。

我们已经知道，这个6个长度的字符串的前后缀最大匹配长度是3了。

现在求这个7个长度的字符串的前后缀匹配长度。

啊，是相同的啊，那皆大欢喜，就在长度为6的字符串的结果的基础上+1就完事了。

但是新加的这个字符，跟长度为6的值的后续那个字符不相同咋办？那就无法使用长度为6的那个值（3）了

意思就是，在这个长度为7的字符串里，前缀跟后缀最长的匹配长度不可能为4了。也不可能比4大，如果比4大的话，那长度为6的字符串的前缀跟后缀最长的匹配长度要比3大了。

这个实际就是在求

很遗憾，我们可以看出来，长度为3的字符串的前缀与后缀最长的匹配长度为0，那这个新加的下标为6的字符，只能跟下标为0的字符进行比较了（从头开始比），ok，比较结果是不相等，那么长度为7的字符串的前缀与后缀最长的匹配长度为0

我们为什么要求前缀与后缀最长的匹配长度这么拗口的变量啊，因为这个值就是下一个字符进行比较的跳跃点啊！

比如我们知道长度为3的字符串，前缀与后缀最长的匹配长度为0，我们就不必再去比较长度为2的字符串，长度为1的字符串是否能跟下标为6的这个字符连起来。而是直接比较下标为0的字符。

class Solution {public int strStr(String haystack, String needle) {if (needle.isEmpty()) return 0;// 分别读取原串和匹配串的长度int n = haystack.length(), m = needle.length();// 原串和匹配串前面都加空格，使其下标从 1 开始// 构建 next 数组，下标为从原串起始位置开始的子串长度，值为该子串的前缀与后缀匹配的最长值int[] next = new int[m+1];//i为子串的长度// 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度int i=2;int j=0;while(i<=needle.length()){while(j>0&&needle.charAt(i-1)!=needle.charAt(j)){j=next[j];}if(needle.charAt(i-1)==needle.charAt(j)){j=j+1;}next[i]=j;i=i+1;}//至此，求得已知子串的最长匹配值，已经求得所有的跳跃点//System.out.println(Arrays.toString(next));int equal_count=0;//开始进行匹配for(int k=0;k<haystack.length();k++){while (equal_count>0&&haystack.charAt(k)!=needle.charAt(equal_count)){equal_count=next[equal_count];}if(haystack.charAt(k)!=needle.charAt(equal_count)){equal_count=0;} else {equal_count=equal_count+1;}if(equal_count==needle.length()){return k-needle.length()+1;}}return -1;}
}