28.找出字符串中第一個匹配項的下標

題目描述

給你兩個字符串haystack和needle，請你在haystack字符串中找出needle字符串的第一個匹配項的下標（下標從0開始）。

如果needle不是haystack的一部分，則返回-1。

解法一：樸素的模式匹配

第一種容易想到的方法就是暴力求解法，也叫做樸素的模式匹配：

簡單的來說就是，從主串hyastack和子串needle的第一個字符開始，將兩字符串的字符一一對比，如果出現(xiàn)某個字符不匹配，主串haystack回溯到第二個字符，子串needle回溯到第一個字符再進行一一對比，如果再次出現(xiàn)某個字符不匹配，則主串回溯到第三個字符，子串回溯到第一個字符…以此類推，直到子串t的字符全部匹配成功。

這道題目最為直觀的解法是：依次枚舉haystack中的每個字符作為[發(fā)起點]，每次從原串(haystack)的[發(fā)起點]和匹配串（needle）的[首位]開始嘗試匹配

• 匹配成功：返回本次匹配的原串的[發(fā)起點]
• 匹配失敗：枚舉原串的下一個[發(fā)起點]，重新嘗試匹配

    public int strStr(String haystack, String needle) {int n = haystack.length();int m = needle.length();for(int i=0;i+m<=n;i++){boolean flag = true;for(int j=0;j<m;j++){if(haystack.charAt(i+j)!=needle.charAt(j)){flag = false;break;}}if(flag){return i;}}return -1;}

解法二：KMP算法

當出現(xiàn)經(jīng)典的字符串匹配時，我們選擇使用KMP算法。

KMP解決的問題類型

kmp算法的作用是在一個已知字符串中查找子串的位置，也叫做串的模式匹配。

比如主串s=“university”，子串t=“sit”。現(xiàn)在我們要找到子串t在主串s中的位置，這點相信大家很容易就看出來了，是在第七個位置。

當然，在字符串非常少的時候，“肉眼觀察法”不失為一個好方法，但如果要你在一千行一萬行文本中找一個單詞，我覺得一般人都找不到。

第一種容易想到的方法就是剛剛的解法一，暴力求解法，也叫做樸素的模式匹配：

簡單的來說就是，從主串s和子串t的第一個字符開始，將兩字符串的字符一一對比，如果出現(xiàn)某個字符不匹配，主串s回溯到第二個字符，子串t回溯到第一個字符再進行一一對比，如果再次出現(xiàn)某個字符不匹配，則主串s回溯到第三個字符，子串s回溯到第一個字符…以此類推，直到子串t的字符全部匹配成功。

但是這個方法真的很慢，因為求一個子串的位置需要太多步驟，而且很多步驟根本沒必要。

這種暴力解法在最好的情況下算法的時間復雜度為O(n)，即子串的n個字符正好等于主串的前n個字符，而最壞的情況下時間復雜度為O(n*m)。但是好在這種算法的空間復雜度為O（1），即不消耗空間而消耗時間。

下面進入正題，KMP算法是如何優(yōu)化這些步驟的。

其實KMP算法的主要思想就是，犧牲空間換時間。

我們回頭看一遍解法一的暴力方式，為什么這么慢呢？是因為我們回溯的步驟太多了，所以我們應該減少回溯的次數(shù)。

怎樣做呢？比如上面第一個圖：當字符’d’與’g’不匹配，我們保持主串的指向不變

主串依然指向’d’，而把子串進行回溯，讓’d’與子串中’g’之前的字符再進行比對。

如果字符匹配，則主串和子串字符同時右移。

至于子串回溯到哪個字符，這個問題我們先放一放。

最長公共前后綴

這里提出一個概念：字符串的最長相等前綴和后綴

舉個例子

字符串a(chǎn)bcdab

前綴的集合：{a，ab，abc，abcd，abcda}

后綴的集合：{b，ab，dab，cdab，bcdab}

此時最長的公共前后綴就是ab

OK，現(xiàn)在我們已經(jīng)會求一個字符串的前綴，后綴，以及公共前后綴了，這個概念很重要。

之前留了一個問題，子串回溯到哪個字符，現(xiàn)在可以著手解決了

KMP算法過程

現(xiàn)在我們看一個圖：第一個長條代表主串，第二個長條代表子串，紅色部分代表兩串中已匹配的部分

綠色和藍色部分分別代表主串和子串中不匹配的字符

現(xiàn)在發(fā)現(xiàn)了不匹配的地方，我們根據(jù)KMP算法的思想，保持主串位置不動，將子串向后移，現(xiàn)在我們要解決的，就是移動多少的問題

之前提到的最長公共前后綴的概念有用處了。

因為紅色部分，即已經(jīng)匹配的部分也會有最長相等前后綴，如下圖

我們發(fā)現(xiàn)，之前“abcab”紅色部分的最長公共前后綴為“ab”，所以，我們把前綴“ab”和后綴“ab”都標成灰色

子串移動的結(jié)果就是讓子串的紅色部分最長相等前綴和主串紅色部分最長相等后綴對齊

這一步弄懂了，KMP算法的精髓我們就掌握了，接下來的流程就是一個簡單的循環(huán)過程。

事實上，每一個字符前的字符串都有最長相等前后綴，而且最長相等前后綴的長度是我們移位的關(guān)鍵，所以我們單獨使用一個next數(shù)組存儲子串的最長相等前后綴的長度，而且next數(shù)組的數(shù)值只與子串本身有關(guān)。

所以，next[i]=j的含義是：下標為i的字符前的字符串最長相等前后綴的長度為j。

我們可以算出上圖中子串“abcabcmn”的next數(shù)組為next[0]=-1（前面沒有字符串單獨處理）

字符	a	b	c	a	b	c	m	n
下標i	0	1	2	3	4	5	6	7
next[i]	-1	0	0	0	1	2	3	0

再看一眼剛剛是哪里出現(xiàn)了不匹配

即s[5]!=t[5]

我們把子串移動，也就是讓s[5]與t[5]前面字符串的最長相等前綴的后一個字符再比較，而next[5] = 2，所以我們讓子串t的第三個字符和剛剛主串的位置對齊開始比較

以此類推，直到將子串匹配完為止

這里我們可以總結(jié)一下，next數(shù)組的作用：

• 1、next[i]的值表示下標為i的字符前的字符串的最長相等先后綴的長度
• 2、表示該處字符不匹配時應該回溯到的字符的下標

next數(shù)組的構(gòu)建

接下來，我們來看看next數(shù)組是如何被預設(shè)出來的。

假設(shè)有匹配串aaabbab，對應的next數(shù)組構(gòu)建過程如下

代碼實現(xiàn)

    public int strStr(String haystack, String needle) {if(needle.isEmpty()){return 0;}//分別讀取原串和匹配串的長度int n = haystack.length(),m = needle.length();//原串和匹配串前面都加空格，使其下標從1開始haystack = " "+haystack;needle = " "+needle;//轉(zhuǎn)成字符數(shù)組char[] s = haystack.toCharArray();char[] p = needle.toCharArray();//構(gòu)建next數(shù)組，數(shù)組長度為匹配串的長度（這是因為next數(shù)組是和匹配串相關(guān)的）int[] next =new int[m+1];//構(gòu)造過程，i=2，j=0開始，i小于等于匹配串的長度for(int i=2,j=0;i<=m;i++){//匹配不成功的話，j=next[j]while(j>0&&p[i]!=p[j+1]){j = next[j];}//匹配成功的話，先讓j++if(p[i]==p[j+1]){j++;}//更新next[i],結(jié)束本次循環(huán)，i++next[i] = j;}//匹配過程，i=1，j=0開始，i小于等于原串長度for(int i=1,j=0;i<=n;i++){//匹配不成功 j=next(j)while(j>0&&s[i]!=p[j+1]){j=next[j];}//匹配成功的話，先讓j++，結(jié)束本次循環(huán)后i++if(s[i]==p[j+1]){j++;}//整一段匹配成功，直接返回下標if(j==m){return i-m;}}return -1;}