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

題目描述

給你兩個(gè)字符串haystack和needle，請(qǐng)你在haystack字符串中找出needle字符串的第一個(gè)匹配項(xiàng)的下標(biāo)（下標(biāo)從0開(kāi)始）。

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

解法一：樸素的模式匹配

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

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

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

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

    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算法

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

KMP解決的問(wèn)題類型

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

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

當(dāng)然，在字符串非常少的時(shí)候，“肉眼觀察法”不失為一個(gè)好方法，但如果要你在一千行一萬(wàn)行文本中找一個(gè)單詞，我覺(jué)得一般人都找不到。

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

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

但是這個(gè)方法真的很慢，因?yàn)榍笠粋€(gè)子串的位置需要太多步驟，而且很多步驟根本沒(méi)必要。

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

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

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

我們回頭看一遍解法一的暴力方式，為什么這么慢呢？是因?yàn)槲覀兓厮莸牟襟E太多了，所以我們應(yīng)該減少回溯的次數(shù)。

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

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

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

至于子串回溯到哪個(gè)字符，這個(gè)問(wèn)題我們先放一放。

最長(zhǎng)公共前后綴

這里提出一個(gè)概念：字符串的最長(zhǎng)相等前綴和后綴

舉個(gè)例子

字符串a(chǎn)bcdab

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

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

此時(shí)最長(zhǎng)的公共前后綴就是ab

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

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

KMP算法過(guò)程

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

綠色和藍(lán)色部分分別代表主串和子串中不匹配的字符

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

之前提到的最長(zhǎng)公共前后綴的概念有用處了。

因?yàn)榧t色部分，即已經(jīng)匹配的部分也會(huì)有最長(zhǎng)相等前后綴，如下圖

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

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

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

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

所以，next[i]=j的含義是：下標(biāo)為i的字符前的字符串最長(zhǎng)相等前后綴的長(zhǎng)度為j。

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

字符	a	b	c	a	b	c	m	n
下標(biāo)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]

我們把子串移動(dòng)，也就是讓s[5]與t[5]前面字符串的最長(zhǎng)相等前綴的后一個(gè)字符再比較，而next[5] = 2，所以我們讓子串t的第三個(gè)字符和剛剛主串的位置對(duì)齊開(kāi)始比較

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

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

• 1、next[i]的值表示下標(biāo)為i的字符前的字符串的最長(zhǎng)相等先后綴的長(zhǎng)度
• 2、表示該處字符不匹配時(shí)應(yīng)該回溯到的字符的下標(biāo)

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

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

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

代碼實(shí)現(xiàn)

    public int strStr(String haystack, String needle) {if(needle.isEmpty()){return 0;}//分別讀取原串和匹配串的長(zhǎng)度int n = haystack.length(),m = needle.length();//原串和匹配串前面都加空格，使其下標(biāo)從1開(kāi)始haystack = " "+haystack;needle = " "+needle;//轉(zhuǎn)成字符數(shù)組char[] s = haystack.toCharArray();char[] p = needle.toCharArray();//構(gòu)建next數(shù)組，數(shù)組長(zhǎng)度為匹配串的長(zhǎng)度（這是因?yàn)閚ext數(shù)組是和匹配串相關(guān)的）int[] next =new int[m+1];//構(gòu)造過(guò)程，i=2，j=0開(kāi)始，i小于等于匹配串的長(zhǎng)度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;}//匹配過(guò)程，i=1，j=0開(kāi)始，i小于等于原串長(zhǎng)度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++;}//整一段匹配成功，直接返回下標(biāo)if(j==m){return i-m;}}return -1;}