大二下半學(xué)期開始了,我們也開始學(xué)起了數(shù)據(jù)結(jié)構(gòu)和算法,所以我打算寫幾篇關(guān)于算法的,所有的題目來(lái)自于hiho網(wǎng)站中的題庫(kù).
歡迎關(guān)注我的博客

• 提示一: KMP的思路
• 提示二: NEXT數(shù)組的使用
• 提示三: 如何求解NEXT數(shù)組

KMP的思路:

當(dāng)兩個(gè)字符串一般匹配時(shí),從頭開始匹配的話,當(dāng)我們遇到不匹配的時(shí)候時(shí),會(huì)從不匹配部分重新匹配.這樣就會(huì)導(dǎo)致我們之前的匹配被白白浪費(fèi),所以KMP算法會(huì)使我們利用之前匹配過(guò)得信息,從而能夠移動(dòng)B串(模式串)跳過(guò)一些字符,從而加快匹配效率.

NEXT使用:

(next 數(shù)組跟最大長(zhǎng)度表對(duì)比后，不難發(fā)現(xiàn)，next 數(shù)組相當(dāng)于“最大長(zhǎng)度值” 整體向右移動(dòng)一位，然后初始值賦為-1。)
KMP的next 數(shù)組相當(dāng)于告訴我們：當(dāng)模式串中的某個(gè)字符跟文本串中的某個(gè)字符匹配失配時(shí)，模式串下一步應(yīng)該跳到哪個(gè)位置。如模式串中在j 處的字符跟文本串在i 處的字符匹配失配時(shí)，下一步用next [j] 處的字符繼續(xù)跟文本串i 處的字符匹配，相當(dāng)于模式串向右移動(dòng) j - next[j] 位
根據(jù)最大長(zhǎng)度表求出了next 數(shù)組后，從而有:
>失配時(shí)，模式串向右移動(dòng)的位數(shù)為：失配字符所在位置 - 失配字符對(duì)應(yīng)的next 值

通過(guò)遞推來(lái)求解NEXT數(shù)組:

1. 如果對(duì)于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相當(dāng)于next[j] = k。
   此意味著什么呢？究其本質(zhì)，next[j] = k 代表p[j] 之前的模式串子串中，有長(zhǎng)度為k 的相同前綴和后綴。有了這個(gè)next 數(shù)組，在KMP匹配中，當(dāng)模式串中j 處的字符失配時(shí)，下一步用next[j]處的字符繼續(xù)跟文本串匹配，相當(dāng)于模式串向右移動(dòng)j - next[j] 位。
   具體參考
   所以求NEXT數(shù)組的代碼為:(c++版):

void getNext(string &substr, vector<int> &next){
next.clear();
next.resize(substr.size());
next[0] = -1;
int j = 0;
int k = -1;
while(j< substr.size()-1){
   if(k == -1||substr[k] == substr[j]){
            j++;
            k++;
            if(substr[k]!=substr[j]){
                next[j] = k;
            }
            else{
                next[j] = next[k];
            }
        }
        else{
            k = next[k];
        }

}
}
以下為hiho的題目代碼:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void getNext(string &substr,vector<int> &next){
    next.clear();
    next.resize(substr.size());
    next[0] = -1;
    int j = 0;
    int k = -1;
    while(j<substr.size()-1){

    if(k == -1||substr[k] == substr[j]){
        j++;
        k++;
        if(substr[k]!=substr[j]){
            next[j] = k;
        }
        else{
            next[j] = next[k];
        }
    }
    else{
        k = next[k];
    }

    }
}
int searchKMP(const string &str,string &substr,vector<int> &next){
    int i = 0;
    int k = -1;
    int cnt = 0;
    int strLen = str.size();
    int substrLen = substr.size();
    getNext(substr,next);

    for(i;i<strLen;++i){

    while(k>-1&&substr[k+1]!=str[i]){
        k = next[k];
    }
    if(substr[k+1] == str[i]){
        ++k;
    }

    if(k == substr.size()-1){
        ++cnt;
    }
}
return cnt;
if(cnt == 0){
    cout<<"no find!"<<endl;
}

}
int main()
{
    int num = 0;
    cin>>num;
    string str, substr;
    vector<int> next;
    int Nkmp[num];
    for(int i = 0;i<num;i++){
    cin >> substr>>str;

Nkmp[i] = searchKMP(str, substr, next);
}
for(int i = 0;i<num;i++){
    cout<<Nkmp[i]<<endl;
}
return 0;

}