Day19：数据结构之串&brute-force算法&--KMP--算法

目录

一、有关串

二、BF算法(暴力匹配算法)

三、KMP算法

1.预备知识：“最长前后缀”

 2.求next数组(core)---部分匹配表的生成

解释一下这边的  j=next[j]

3.KMP算法

一、有关串

• 实现串需要存储空间和当前大小

• 串没有'\0'，没有把'\0'拷贝进去，c++的 string 不能直接用 %s 形式打印，自己实现的串也不能用 %s 打印

• 串没有'\0'，用curSize作为结束标记(伪删除)：串的连接、串的拷贝、串的比较

• 串的实现代码

  #include 
  #include 
  #include 
  #include 
   
  #define MAX  1024
  typedef struct 
  {
  	char mem[MAX];
  	int curSize;
  	//int maxSize;
  }string,*LPSTR;
  LPSTR  createstring(const char* str) 
  {
  	LPSTR pstr = (LPSTR)malloc(sizeof(string));
  	assert(pstr);
  	for (int i = 0; i < MAX; i++) 
  	{
  		pstr->mem[i] = '\0';
  	}
  	int count = 0;
  	while (str[count] != '\0') 
  	{
  		pstr->mem[count] = str[count];
  		count++;
  	}
  	pstr->curSize = count;
  	return pstr;
  }
  //串的插入
  void insertstring(LPSTR pstr, const char* str, int len, int pos) 
  {
  	if (pos < 0 || pos >= MAX) 
  	{
  		printf("无效下标!\n");
  		return;
  	}
  	if (pstr->curSize + len >= MAX) 
  	{
  		printf("太长，无法插入!\n");
  		return;
  	}
  	if (pos > pstr->curSize) 
  	{
  		for (int i = 0; i < len; i++) 
  		{
  			pstr->mem[pstr->curSize++] = str[i];
  		}
  	}
  	else 
  	{
  		//1.腾位置
  		for (int i = pstr->curSize; i >= pos; i--) 
  		{
  			pstr->mem[len + i] = pstr->mem[i];
  		}
  		//2.插入新的字符串
  		for (int i = 0; i < len; i++) 
  		{
  			pstr->mem[pos + i] = str[i];
  		}
  		pstr->curSize += len;
  	}
  }
  void printstring(LPSTR pstr) 
  {
  	for (int i = 0; i < pstr->curSize; i++) 
  	{
  		putchar(pstr->mem[i]);
  	}
  	putchar('\n');
  }
  //串的删除
  //只做区间删除(通过下标)
  //匹配删除(BF+KMP)
  void deletestring(LPSTR pstr, int start, int end)
  {
  	if (start > end || end > pstr->curSize || start <= 0) 
  	{
  		printf("区间有误!\n");
  		return;
  	}
  	int count = end - start + 1;
  	for (int i = end, j = start - 1; i < pstr->curSize; i++, j++) 
  	{
  		pstr->mem[j] = pstr->mem[i];
  	}
  	//伪删除，手动置0
  	for (int i = pstr->curSize; i >= pstr->curSize - count; i--) 
  	{
  		pstr->mem[i] = '\0';
  	}
  	pstr->curSize -= count;
  }
  

二、BF算法(暴力匹配算法)

//BF算法
int BF(LPSTR pstr1, LPSTR pstr2) 
{
	int index = 0;	//记录序号，返回找到的位置
	int i = 0;
	int j = 0;
	while (pstr1->mem[i] != '\0' && pstr2->mem[j] != '\0') 
	{
		if (pstr1->mem[i] == pstr2->mem[j])  //相等往下比较
		{
			i++;
			j++;
		}
		else 
		{
			index++;			//记录的是要匹配到字符串的下标
			i = index;
			j = 0;				//不匹配还原位置
		}
	}
	if (pstr2->mem[j] == '\0'){return index;}
	return -1;
}

 三、KMP算法

1.预备知识：“最长前后缀”

 2.求next数组(core)---部分匹配表的生成

        部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度

上述的子串生成的匹配表为:   -1 [0 . 0. 0. 0. 1. 2. 0.]

void getNext(LPSTR pstr, int next[]) 
{
 
	int len = pstr->curSize;
	int i = 0;
	int j = -1;
	next[0] = -1;
	while (i < len) 
	{
		//通过j避免了-1下标
		if (j == -1 || pstr->mem[i] == pstr->mem[j]) 
		{
			i++;
			j++;
			next[i] = j;			//部分匹配元素的长度
		}
		else 
		{
			j = next[j];			//重置j为-1
		}
	}
}

 i是扫描后缀的，j 是扫描前缀的。

解释一下这边的  j=next[j]

        此处i已经扫到了B,j的值为3刚赋给A对应的next[]的位置，看到无法构成4个相同的最长前后缀,于是，j=next[j]进行跳转,j=next[3]--->j=1（这边是从-1作为next数组的第一个）,下次进循环比较的就是str[1]和str[7] 'b'发现相等，---->j++ 所以j=2   B对应next数组中的位置也是2结束。值得一提,若第二次str[1]和str[7]同样匹配失败了--->j=next[j](即next[1]=0，则j=0赋值给B对应位置)--->此后next[j]=-1，而且i已经到了最后，循环结束。

        什么意思呢？第一次回跳是干嘛?为啥让j跳到原来的next[j]的位置，因为想利用之前扫描过的信息，既然前缀长度=4已经达不成了，退而求其次，想看看有没有更小的前缀长！

用暴力吗？NO!!! --->利用之前扫描过了的信息，看能否利用--->本次跳转对应的子串由于是相同子串，所以一定是前缀的最后一个位置，即j=1发现两者str[1=j]和str[7=i]相等了。于是j++，给next完成赋值

         再说说这个案例： -1 [0 . 0. 0. 0. 1. 2. 0.] j=2时，计算到了D，发现并不能构成前缀长为3，所以跳转  j=next[j]---->next[2]=0所以j=0，然后再进入循环比较，str[0]!=str[i]所以再次进入了跳转，j=next[j]--->j=-1然后符合第一个j==-1，所以j++--->j=0完成对next数组的最后一次赋值。

3.KMP算法：

int KMP(LPSTR pstr1, LPSTR pstr2, int next[])
{
	getNext(pstr2, next);
	int i = 0;
	int j = 0;
	while (i < pstr1->curSize && j < pstr2->curSize) 
	{
		if (j == -1 || pstr1->mem[i] == pstr2->mem[j]) 
		{i++;j++;}//相同直接都++即可
		else //存在不一样的,根据匹配表进行匹配回退。
		    j = next[j];
	}
	if (j == pstr2->curSize) 
	{return i - j;}//返回当前回合第一次匹配的位置。
	return -1;//没有匹配成功
}

匹配过程图解：

 这边硬是让j退到了0的位置next[-1]赋值给j=-1--->进入第一个循环i++  j++