大二下半学期开始了,我们也开始学起了数据结构和算法,所以我打算写几篇关于算法的,所有的题目来自于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数组:
- 如果对于值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;
}
