28. 找出字符串中第一個匹配項的下標(biāo)

莫得思路……好久沒做題，都已經(jīng)忘得差不多了

看答案

其實就是自己寫一個String的indexOf函數(shù)，它的作用是返回某個字符串在另一個字符串中首次出現(xiàn)的位置。

利用的思想是KMP

KMP

例子：
要在文本串：aabaabaafa 中查找是否出現(xiàn)過一個模式串：aabaaf。

KMP主要應(yīng)用在字符串匹配上。

KMP的主要思想是當(dāng)出現(xiàn)字符串不匹配時，可以知道一部分之前已經(jīng)匹配的文本內(nèi)容，可以利用這些信息避免從頭再去做匹配了。

next數(shù)組（前綴表）

next數(shù)組就是一個前綴表（prefix table）。

前綴表有什么作用呢？

前綴表是用來回退的，它記錄了模式串與主串(文本串)不匹配的時候，模式串應(yīng)該從哪里開始重新匹配。

那么什么是前綴表：記錄下標(biāo)i之前（包括i）的字符串中，有多大長度的相同前綴后綴。

最長公共前后綴

文章中字符串的前綴是指不包含最后一個字符的所有以第一個字符開頭的連續(xù)子串。

后綴是指不包含第一個字符的所有以最后一個字符結(jié)尾的連續(xù)子串。

正確理解什么是前綴什么是后綴很重要!

所以字符串a(chǎn)的最長相等前后綴為0。 字符串a(chǎn)a的最長相等前后綴為1。 字符串a(chǎn)aa的最長相等前后綴為2。 等等…

匹配的過程在下標(biāo)5的地方遇到不匹配，模式串是指向f：

然后應(yīng)該找到了下標(biāo)2，指向b，繼續(xù)匹配：如圖：

以下這句話，對于理解為什么使用前綴表可以告訴我們匹配失敗之后跳到哪里重新匹配 非常重要！

下標(biāo)5之前這部分的字符串（也就是字符串a(chǎn)abaa）的最長相等的前綴 和 后綴字符串是 子字符串a(chǎn)a ，因為找到了最長相等的前綴和后綴，匹配失敗的位置是后綴子串的后面，那么我們找到與其相同的前綴的后面重新匹配就可以了。

所以前綴表具有告訴我們當(dāng)前位置匹配失敗，跳到之前已經(jīng)匹配過的地方的能力。

如何計算前綴表

長度為前1個字符的子串a(chǎn)，最長相同前后綴的長度為0。

長度為前2個字符的子串a(chǎn)a，最長相同前后綴的長度為1。

長度為前3個字符的子串a(chǎn)ab，最長相同前后綴的長度為0。

以此類推： 長度為前4個字符的子串a(chǎn)aba，最長相同前后綴的長度為1。 長度為前5個字符的子串a(chǎn)abaa，最長相同前后綴的長度為2。 長度為前6個字符的子串a(chǎn)abaaf，最長相同前后綴的長度為0。

那么把求得的最長相同前后綴的長度就是對應(yīng)前綴表的元素，如圖：

找到的不匹配的位置， 那么此時我們要看它的前一個字符的前綴表的數(shù)值是多少。

然后移動到，從前一個字符處開始，它對應(yīng)的前綴表是多少，就向前移多少個位置（不包括前一個元素本身），所以移動到b處

其實這里移動到的位置就是前綴表的元素代表的位置，不用前移多少個元素，比如aabaaf中，f處不匹配，應(yīng)該移動到它的前一個元素a對應(yīng)的前綴表元素所指的位置，即字符串下標(biāo)為2的元素處，即b。

前綴表與next數(shù)組

很多KMP算法的時間都是使用next數(shù)組來做回退操作，那么next數(shù)組與前綴表有什么關(guān)系呢？

next數(shù)組就可以是前綴表，但是很多實現(xiàn)都是把前綴表統(tǒng)一減一（右移一位，初始位置為-1）之后作為next數(shù)組。

其實這并不涉及到KMP的原理，而是具體實現(xiàn)，next數(shù)組既可以就是前綴表，也可以是前綴表統(tǒng)一減一（右移一位，初始位置為-1）。

時間復(fù)雜度分析

其中n為文本串長度，m為模式串長度，因為在匹配的過程中，根據(jù)前綴表不斷調(diào)整匹配的位置，可以看出匹配的過程是O(n)，之前還要單獨生成next數(shù)組，時間復(fù)雜度是O(m)。所以整個KMP算法的時間復(fù)雜度是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數(shù)組public void getNext(int[] next,String s){int j=0;for(int i=1;i<s.length();i++){//因為要得到前后相等的公共字符串，而next的0位置的元素//一定是0，所以i取1，也就是從next數(shù)組的1號元素開始填充while(j>0&&s.charAt(i)!=s.charAt(j)){j=next[j-1];//回退到前個元素的next數(shù)組處}if(s.charAt(i)==s.charAt(j)){j++;}next[i]=j;}}
}