以下是能用KMP求解的算法題，KMP是用于字符串匹配的經(jīng)典算法【至今沒學(xué)懂………啊啊啊】
28. 找出字符串中第一個匹配項的下標
題目鏈接：28. 找出字符串中第一個匹配項的下標
題目內(nèi)容：
題意還是很好理解的，要在字符串haystack中查找一個完整的needle，即字符串匹配。
暴力求解
暴力求解就是用兩層循環(huán)：haystack從第i個字符開始，needle從第一個字符開始j = 0，之后依次判斷needle[j]和haystack[j+i]是否相等。如果不相等，說明haystack中從第i位開始的子串和needle是不匹配的。之后j要回溯到j(luò) = 0，i向后移動一位。代碼實現(xiàn)（C++）：
class Solution {
public:
int strStr(string haystack, string needle) {
//haystack下標最大值
int n = haystack.size() - needle.size();
//外層是haystack從下標i開始和needle逐字符比較
for(int i = 0 ; i <= n; i++){
int j = 0;
//needle從j=0開始
while( j < needle.size()){
//如果有相等就退出循環(huán)，開啟下一輪
if(haystack[j+i] != needle[j])
break;
j++;
}
//如果是遍歷完needle都與從i開始的子串相同，就找到了
if(j == needle.size())
return i;
}
return -1;
}
};
KMP
暴力求解中，如果當前的needle[j]和haystack[j+i]不匹配，needle中j會回退到0，haystack中i+j回退到i+1，這里是可以優(yōu)化的，KMP就是為了減少這樣的回溯。
KMP是用于求解字符串匹配的算法，在當前needle[j]和haystack[j+i]不匹配時，能夠快速找到j(luò)應(yīng)該移動到的位置，而不是直接回溯到開頭。比如下面圖中s[i]和p[j]不匹配后，由于p[j]前面的子串的前綴ab和后綴ab相同，因此j不需要回溯到0，是移動到abc中c的位置，繼續(xù)和s[i]比較。
KMP中一個重點是最長相同前后綴長度。什么是前綴：一個字符串從第一個字符開始的，不包括最后一個字符的子串；什么是后綴：一個字符串中從最后一個字符開始的，不包括第一個字符的子串。
最長相同前后綴長度，就是一個字符串中相同的前后綴里面，最長的一組的長度。比如下圖里對于ababa這個字符串，相同前后綴有兩組，但是我們需要最長那組的長度。因為字符串匹配過程中，S[i]和P[j]不匹配時，j是要根據(jù)P[j]前面子串的前后綴長度來回退的，選擇最長前后綴能夠保證不遺漏答案。
KMP算法需要求模式串P的next數(shù)組，實際上這個next數(shù)組記錄的就是P所有從第一個字符開始的子串的最長相同前后綴的長度：next[i]表示下標0到下標i這段子串的，最長相同前后綴的長度。假設(shè)有next[i-1]=m，那么next[i] <= next[i-1]+1，其中取等需要P[next[i-1]] == P[i]?！疽驗閚ext[i-1]里面存的是長度，當作下標的時候就是最長相同前后綴里面那個前綴后面一個字符；而P[i]就是P[i-1]最長相同前后綴的后綴的后后面一個字符】。
如果P[next[i-1]] != P[i]，那么就要判斷P[next[next[i-1]-1]]和P[i]的關(guān)系，直到下標回溯到0或者找到了和P[i]匹配的位置。
代碼如下（C++）：
ector<int> Kmp_Next(string s){
int n = s.size();
vector<int> next(n, 0);
//next數(shù)組中存的是對應(yīng)下標處子串【包括下標位置】的最長前后綴的長度
next[0] = 0;
for(int i = 1; i < n; i++){
int j = next[i-1];
while(j>0 && s[j] != s[i]) //不匹配就循環(huán)回退
j = next[j-1];
if(s[i] == s[j]) //如果匹配，長度在j的基礎(chǔ)上+1
j++;
next[i] = j;
}
return next;
}
KMP的匹配過程：首先求得了模式串P的next數(shù)組，即每個P[0]~P[i]這一段這串中最長的相同前后綴的長度；然后P中的字符從P[j=0]開始，S中的字符也從S[pos=0]開始，判斷S[pos]和P[j]是否匹配，如果匹配就j++，pos++向后移動；如果不匹配，j就根據(jù)next[j-1]回退，并判斷回退后新的下標j對應(yīng)的P[j]和S[pos]是否匹配，如果不匹配繼續(xù)回退，直到匹配或者j=0。實現(xiàn)過程如下：
- 要先找到P中哪個字符和當前的S[pos]匹配。因為如果P[j] != S[pos]，j需要根據(jù)next數(shù)組循環(huán)回退j = next[j-1]，那么就先找到能夠匹配的j，才停止；
while(j>0 && haystack[pos] != needle[j])
j = next[j-1];
- 上面循環(huán)退出有兩種情況，P[j] == S[pos]或者j == 0；如果是前者，自然pos++，j++；如果是后者，就只有pos++；
if(haystack[pos] == needle[j]){
pos++;
j++;
}
else
pos++;
- 最后停止要么是j遍歷到了最后，要么是pos遍歷到了最后。只有j遍歷到最后才算完全匹配；
完整代碼如下（C++）：
class Solution {
public:
//先求needle的next數(shù)組
vector<int> Kmp_Next(string s){
int n = s.size();
vector<int> next(n, 0);
//next數(shù)組中存的是對應(yīng)下標處子串【包括下標位置】的最長前后綴的長度
next[0] = 0;
for(int i = 1; i < n; i++){
int j = next[i-1];
while(j>0 && s[j] != s[i])
j = next[j-1];
if(s[i] == s[j])
j++;
next[i] = j;
}
return next;
}
int strStr(string haystack, string needle) {
vector<int> next = Kmp_Next(needle);
int pos = 0, j = 0;
//kmp匹配過程
while(j < needle.size() && pos < haystack.size()){
while(j>0 && haystack[pos] != needle[j])
j = next[j-1];
if(haystack[pos] == needle[j]){
pos++;
j++;
}
else
pos++;
}
//needle沒有遍歷完，pos已經(jīng)遍歷完haystack了，沒有匹配的地方
if(j < needle.size())
return -1;
//needle遍歷完，有匹配的地方
else
return pos - needle.size();
}
};
459. 重復(fù)的子字符串
題目鏈接：459. 重復(fù)的子字符串
題目內(nèi)容：
暴力求解
題目要求我們判斷字符串S是不是由其某個子串重復(fù)構(gòu)成的。假設(shè)子串m能夠重復(fù)構(gòu)成S，那么S可以表示m/mm/m/……這樣的形式，即由n個m組成【n≥2】。分析這樣的子串有兩個特點：
- 從第一個字符開始；
- 長度≤S.size()/2；
- S.size()一定能夠被m.size()整除；
根據(jù)子串的這兩個特點，我們可以去判斷所有這樣的子串，子串長度從1開始，最多有S.size()/2這么多個。針對每個子串，先判斷其長度能否整除S的長度；再判斷其能否重復(fù)構(gòu)成S——將S分成和子串m一樣長度的k個子串，所有的子串和m對比是否一樣，如果有一個不一樣就直接break。
代碼如下（C++）：
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int size = s.size();
//end是子串m的長度
for(int end = 1; end <= size/2; end++ ){
//s長度能夠被end整除才繼續(xù)下面的判斷
if(size % end == 0){
int i;
//剩下的子串和m對比
for(i = end ; i < size ; i += end ){
if(s.substr(0,end) != s.substr(i, end))
break;
}
if(i == size )
return true;
}
}
return false;
}
};
暴力求解的時間復(fù)雜度是O(n^2)。
在S+S中找S
假設(shè)S由n個子串m組成【n≥2】，那么S+S中有2n個m，將S+S去頭去尾【刪除第一個和最后一個元素就能實現(xiàn)去掉一個m和最后一個m】后還有2n-2個m，由于n≥2，2n-2≥n。那么如果S+S去頭去尾后還能有至少一個完整的S，就能證明其是由m循環(huán)組成的。代碼實現(xiàn)（C++）【就一句話】：
class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s+s).find(s,1) != s.size() ? true : false;
}
};
那么如果不是由子串m循環(huán)組成的字符串，S+S去頭去尾以后一定找不到一個完整的S嗎？【emm需要再研究一下】文章來源：http://www.zghlxwxcb.cn/news/detail-700723.html
686. 重復(fù)疊加字符串匹配
題目鏈接：686. 重復(fù)疊加字符串匹配
題目內(nèi)容：
理解題意，可以發(fā)現(xiàn)題目還是要求我們做字符串匹配。只是查詢串不是簡單的a，而是a的疊加，并且這個疊加次數(shù)是不確定的。
首先我們要明確方法，字符串匹配，首選KMP算法。a的疊加在匹配中可以用a[i % a.size()]來解決。 如果a的m次疊加后，能夠查詢到b，之后的m+1，m+2次疊加b也是其子串， 因此m就是最小的疊加次數(shù)。并且如果能夠找到這樣的m使得b成為a的m次疊加后的子串的話，kmp查詢就能成功，b會被遍歷完。但是如果不能的話，由于a的疊加用a[i % a.size()]，a的下標永遠不會越界，b也一直不會遍歷結(jié)束，那么kmp中的循環(huán)該如何結(jié)束？
假設(shè)當前s和b開始匹配的位置是在第一個a之后，因為查詢串s是a重復(fù)循環(huán)疊加的，那么說明在這之前和第一個a也是同樣能夠完成當前的部分匹配的。但是會從第一個a的匹配變到第二個，就說明在當前匹配的字符后有不能匹配的，那么就會繼續(xù)變到第三個a，這樣下去是永遠也不能完全匹配的，即b不是a的循環(huán)疊加的子串。因此得出結(jié)論：s和b開始匹配的地方不是在第一個a中話，可以肯定b不是s的子串，只有b從第一個a中的字符開始匹配才有可能匹配成功。即a中下標i，b中下標 j，如果 **i - j >= a.size()**就說明匹配不上。
代碼如下（C++）：文章來源地址http://www.zghlxwxcb.cn/news/detail-700723.html
class Solution {
public:
//KMP算法
int strStr(string haystack, string needle) {
int len_h = haystack.size();
int len_n = needle.size();
//求模式串的vector數(shù)組
vector<int> next(len_n, 0);
//next數(shù)組中存的是對應(yīng)下標處子串【包括下標位置】的最長前后綴的長度
for(int i = 1; i < len_n; i++){
int j = next[i-1];
while(j>0 && needle[j] != needle[i])
j = next[j-1];
if(needle[i] == needle[j])
j++;
next[i] = j;
}
//開始匹配
int pos = 0, j = 0;
//結(jié)束條件
while(pos - j < len_h){
while(j>0 && haystack[pos % len_h] != needle[j])
j = next[j-1];
if(haystack[pos % len_h] == needle[j]){
pos++;
j++;
}
else
pos++;
//因為pos可以無限增加，當遍歷完b的時候說明已經(jīng)找到了
if(j == len_n)
return pos;
}
return -1;
}
int repeatedStringMatch(string a, string b) {
int idx = strStr(a, b);
if(idx == -1)
return -1;
//求m
return (idx-1) / a.size() + 1;
}
};
到了這里，關(guān)于【leetcode 力扣刷題】字符串匹配之經(jīng)典的KMP！??！的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
