代码随想录第十天（28）

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

莫得思路……好久没做题，都已经忘得差不多了

看答案

其实就是自己写一个String的indexOf函数，它的作用是返回某个字符串在另一个字符串中首次出现的位置。

利用的思想是KMP

KMP

例子：
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

KMP主要应用在字符串匹配上。

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

next数组（前缀表）

next数组就是一个前缀表（prefix table）。

前缀表有什么作用呢？

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

那么什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

最长公共前后缀

文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

正确理解什么是前缀什么是后缀很重要!

所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等…

匹配的过程在下标5的地方遇到不匹配，模式串是指向f：

然后应该找到了下标2，指向b，继续匹配：如图：

以下这句话，对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配 非常重要！

下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

如何计算前缀表

长度为前1个字符的子串a，最长相同前后缀的长度为0。

长度为前2个字符的子串aa，最长相同前后缀的长度为1。

长度为前3个字符的子串aab，最长相同前后缀的长度为0。

以此类推： 长度为前4个字符的子串aaba，最长相同前后缀的长度为1。 长度为前5个字符的子串aabaa，最长相同前后缀的长度为2。 长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0。

那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图：

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。

然后移动到，从前一个字符处开始，它对应的前缀表是多少，就向前移多少个位置（不包括前一个元素本身），所以移动到b处

其实这里移动到的位置就是前缀表的元素代表的位置，不用前移多少个元素，比如aabaaf中，f处不匹配，应该移动到它的前一个元素a对应的前缀表元素所指的位置，即字符串下标为2的元素处，即b。

前缀表与next数组

很多KMP算法的时间都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢？

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。

其实这并不涉及到KMP的原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

时间复杂度分析

其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。

暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。

class Solution {public int strStr(String haystack, String needle) {int[] next=new int[needle.length()];next[0]=0;getNext(next,needle);int j=0;for(int i=0;i<haystack.length();i++){//这里的i是从0开始，此时的目的是要将//长的字符串和短的字符串从0号位置开始比较while(j>0&&haystack.charAt(i)!=needle.charAt(j)){j=next[j-1];}if(haystack.charAt(i)==needle.charAt(j)){j++;}if(j==needle.length()){return i-needle.length()+1;}}return -1;}//获得next数组public void getNext(int[] next,String s){int j=0;for(int i=1;i<s.length();i++){//因为要得到前后相等的公共字符串，而next的0位置的元素//一定是0，所以i取1，也就是从next数组的1号元素开始填充while(j>0&&s.charAt(i)!=s.charAt(j)){j=next[j-1];//回退到前个元素的next数组处}if(s.charAt(i)==s.charAt(j)){j++;}next[i]=j;}}
}