大二下半学期开始了,我们也开始学起了数据结构和算法,所以我打算写几篇关于算法的,所有的题目来自于hiho网站中的题库.
欢迎关注我的博客

• 提示一: KMP的思路
• 提示二: NEXT数组的使用
• 提示三: 如何求解NEXT数组

KMP的思路:

A串:	BBC ABCDAB ABCDABCD
B串:	ABCDABD ->

当两个字符串一般匹配时,从头开始匹配的话,当我们遇到不匹配的时候时,会从不匹配部分重新匹配.这样就会导致我们之前的匹配被白白浪费,所以KMP算法会使我们利用之前匹配过得信息,从而能够移动B串(模式串)跳过一些字符,从而加快匹配效率.

NEXT使用:

(next 数组跟最大长度表对比后，不难发现，next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。)
KMP的next 数组相当于告诉我们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟文本串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位
根据最大长度表求出了next 数组后，从而有:
>失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值

通过递推来求解NEXT数组:

1. 如果对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于next[j] = k。
   此意味着什么呢？究其本质，next[j] = k 代表p[j] 之前的模式串子串中，有长度为k 的相同前缀和后缀。有了这个next 数组，在KMP匹配中，当模式串中j 处的字符失配时，下一步用next[j]处的字符继续跟文本串匹配，相当于模式串向右移动j - next[j] 位。
   具体参考
   所以求NEXT数组的代码为:(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;

}