串匹配算法——KMP (algorithm for KMP)

• tips:
  我们知道字符串操作的不可避免的问题就是求出待匹配的字符串在主串中的位置（即首次出现的下标），目前已知的有两种主流的串模式匹配算法——暴力匹配和kmp模式匹配算法。

学习本节内容需要预备的知识（可以自行上网查阅哦）

• 字符串的表示
• 字符串的前后缀（不同位置）
• KMP算法的原理
• 什么是next数组
• 什么是nextval数组（KMP的改进）

• summary：(discrepancy of two method)
  moderate tactics:

KMP tactics:

• Now that you have learned the idea of KMP and violent match algorithm. follows are two tactics’s realization for me with C++. I hope it will enhance you much.

• violent match:

#include
using namespace std;
#define maxn 1024
//暴力匹配
//匹配串在珠主串进行匹配
//成功两个串的指针后移
//失败的话主串指针跑到本次开始匹配的下个位置，匹配串指针回到本串的起始位置
//当主串或匹配串任意一个的指针超过其串长就退出匹配
//如果匹配串的指针大于串长匹配成功返回开始匹配的位置（匹配成功）
//否则匹配失败返回-1 
char *s,*t;

//暴力匹配算法 
int violent_match(char *mainStr,char *assistantStr);


int main(){
	s=new char[maxn];
	t=new char[maxn];
	scanf("%sn%s",s,t);
	int pos=violent_match(s,t);
    if(pos==-1) printf("匹配失败了哦！");
	else printf("匹配字符串在主串中的首次出现的位置是：%d",pos); 
	return 0;
} 

int violent_match(char *mainStr,char *assistantStr){
	int lens=strlen(mainStr);
	int lent=strlen(assistantStr);
	int i=0,j=0;
	while(i
		if(s[i]!=t[j]){
			i=i-j+1;
			j=0;
		}else {i++; j++;}
	} 
	if(j>=lent) return i-lent;//成功 
	else return -1;//失败 
}

• KMP

//kmp算法的实现

#include
#define maxn 1024
using namespace std;

char *s, *t;
int *my_next;
int len;
int *next_val;

//获得 next数组
void getNext(int *next_arr);
//kmp
int kmp();
void show(int *next_arr);
void getnextVal() {//next数组的优化，大部分考试不要求掌握 
	next_val = new int[maxn];
	next_val[0] = -1;
	cout<<"nextval 数组入下："<
		if (t[i] == t[my_next[i]]) next_val[i] = next_val[my_next[i]];
		else next_val[i] = my_next[i];
	}
	show(next_val);
}

int main() {
	s = new char[maxn];
	t = new char[maxn];
	my_next = new int[maxn];
	memset(my_next, 0, sizeof(int)*maxn);
	scanf("%sn%s", s, t);
	cout << s << endl;
	cout << t << endl;
	len = strlen(t);
	getNext(my_next);
	cout<<"next 数组如下："<
	for (int i = 0; i < len; i++)
		cout << next_arr[i] << " ";
	cout << endl;
}

int kmp() {
	int i = 0, j = 0;
	int length1 = strlen(s);
	int length2 = strlen(t);
	while (i < length1 && j < length2) {
		if (j == -1 || s[i] == t[j]) {
			i++;
			j++;
		} else j = my_next[j];
	}
	cout << "i is:" << i << endl;
	cout << "j is:" << j << endl;
	if (j >= strlen(t)) return i - length2;
	else return -1;
}

void getNext(int *next_arr) {
	int i = 0, j = -1;
	next_arr[0] = -1;
	while (i < len) {
		if (j == -1 || t[i] == t[j]) {
			i++;
			j++;
			next_arr[i] = j;
		} else j = next_arr[j];
	}
}

I confirm that the goal of being admitted to graduate school will come true next year! come on!!!

• 2022/5/30