字符串匹配算法BF和KMP

BF朴素匹配

时间复杂度 \(O(n*m)\)

int BF_Search(const string &txt,const string &pat){ //匹配成功，返回下标，否则返回-1
	int lt = txt.length(); 
	int lp = pat.length();
	int i = 0,j = 0;
	while(i < lt && j < lp){
		if(txt[i] == pat[j]) {i++ ; j++;}
		else {i -= j-1 ; j = 0;}
	}
	if(j == lp) return i-lp;
	return -1;
}

KMP算法

时间复杂度 $ O(n+m)$

#define MAXLEN 1000
int Next[MAXLEN];

void GetNext(const string &pat,int Prefix[]){
	int len = pat.length();
    Prefix[0] = 0;
    // 这里的Prefix[i]是以i为末位的最长公共前后缀
    // 因为前后缀不允许重叠，所以Prefix[0]必然为0，作为终止条件
	int j = 0;
	for(int i = 1 ; i < len ; i ++){
		while(j > 0 && pat[i] != pat[j]){j = Prefix[j-1];}//当pat[i] != pat[j]时，需要将j回退到Prefix[j-1]（这是公共前后缀更短的唯一的可能性，避免了重复计算）。若此处的j已经回退到0,则没有更短的可能，循环终止。
		if(pat[i] == pat[j]){j++;} //若相等，继续遍历
		Prefix[i] = j; //记录Prefix[i]
	}
}

int KMP_Search(const string &txt,const string &pat){
	int lt = txt.length();
	int lp = pat.length();
	int i = 0; //i是后缀末尾
	int j = 0; //j是前缀末尾
	while(i < lt && j < lp){ //如果i == lt,说明找不到pat；如果j == lp，说明找到了
		if(txt[i] == pat[j]){i++;j++;}//如果相等，继续匹配下一位
         else if(j == 0) i++; 
		else {j = Next[j-1];}//否则，j回退到Next[j-1];
	}
	if(j == lp) return i-lp; //如果找到，返回i-lp，即pat在txt中的首下标
	return -1;//如果没找到，返回-1
}

KMP统计子串个数

int KMPSearchCount(const string & txt,const string & pat){
	int lt = txt.length();
	int lp = pat.length();
	int i = 0;
	int j = 0;
	int cnt = 0;
	while(i < lt && j < lp){
		if(txt[i] == pat[j]){i++;j++;}
		else if(j == 0 ){i++;}
		else {j = Prefix[j-1];}
		if(j == lp){i -= (lp-1);j=0;cnt++;}//主要是这里改动了一句
	}
	return cnt;
}

模板题

P3375 【模板】KMP - 洛谷 | 计算机科学教育新生态

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

int Next[maxn],lp,lt;
bool f[maxn];
string pat,txt;

void getNext(){
	Next[0] = 0;
	for(int i = 1, j = 0 ; i < lp ; i ++){
		while(j > 0 && pat[j] != pat[i]){j = Next[j-1];};
		if(pat[j] == pat[i]){j++;}
		Next[i] = j;
	}
}

bool kmp(){
	int i = 0, j = 0;
	while(i < lt && j < lp){
		if(txt[i] == pat[j]){i++;j++;}
		else if(j > 0) {j = Next[j-1];}
		else {i++;}
		if(j == lp){f[i-lp] = true; i -= (lp-1); j = 0;}
        // 注意这里i不能++,而是 -= lp-1, 前者会遗漏重叠部分
	}
	return j == lp;
}

int main(void){
	cin>>txt>>pat;
	lt = txt.length();
	lp = pat.length();
	getNext(); kmp();
	for(int i = 0 ; i < lt ; i ++){
		if(f[i]) cout<<i+1<<"\n";
	}
	for(int i = 0 ; i < lp ; i ++){
		cout<<Next[i]<<" ";
	}
	return 0;
}