2022年考研数据结构_4 串

ゞ浴缸里的玫瑰 2022-12-31 05:22 219阅读 0赞

https://gitee.com/fakerlove/Data-Structure

### 文章目录 ###

*  4. 串
 *   *  4.1 模式匹配
     *   *  1. 暴力算法 bf
         *  2. KMP 算法
         *   *  前缀，后缀，部分匹配值
             *  next 数组 (子串回溯的位置)
             *  代码

# 4. 串 #

## 4.1 模式匹配 ##

### 1. 暴力算法 bf ###

**从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。这有什么难的？**

![6fbf00f2a856d55f6769b38352d1146f.png][]

匹配不成功，i回溯到开始，j 回溯到子串的开头

![c246cfa0bace7adde6ea58d47d317ebd.png][]

匹配不成功，i 往后走

![eecf73237e14166b68662ef5f2c4c680.png][]

![bb91d4c19da6787cf123509c05fceb59.png][]

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

### 2. KMP 算法 ###

利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置

时间复杂度O(m+n)

#### 前缀，后缀，部分匹配值 ####

*  前缀：除去最后一个字符外，字符串的所有头部子串
 *  后缀：除去第一个字符外，字符串的所有头部子串
 *  部分匹配值：字符串的前缀和后缀最长相等的前后缀长度

<table> 
 <thead> 
  <tr> 
   <th>字符串</th> 
   <th>部分匹配值</th> 
   <th>前缀</th> 
   <th>后缀</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>a</td> 
   <td>0 (空集 空集)</td> 
   <td>空集</td> 
   <td>空集</td> 
  </tr> 
  <tr> 
   <td>ab</td> 
   <td>0 {a} {b}</td> 
   <td>a</td> 
   <td>b</td> 
  </tr> 
  <tr> 
   <td>aba</td> 
   <td>1 {a,ab} {ba,a}</td> 
   <td>ab a</td> 
   <td>ba a</td> 
  </tr> 
  <tr> 
   <td>abab</td> 
   <td>2 {a,ab,aba} {b,ab,bab}</td> 
   <td>a ab aba</td> 
   <td>b ab bab</td> 
  </tr> 
  <tr> 
   <td>ababa</td> 
   <td>3 {a,ab,aba,abab} {a,ba,aba,baba}</td> 
   <td>a ab aba abab</td> 
   <td>a ba aba baba</td> 
  </tr> 
  <tr> 
   <td>ababc</td> 
   <td>0 {a,ab,aba,abab} {c,bc,abc,babc}</td> 
   <td>a,ab,aba,abab</td> 
   <td>c,bc,abc,babc</td> 
  </tr> 
  <tr> 
   <td>sssss</td> 
   <td>4</td> 
   <td>s,ss,sss,ssss</td> 
   <td>s,ss,sss,ssss</td> 
  </tr> 
  <tr> 
   <td>abca</td> 
   <td>1 {a,ab,abc} {a,ca,bca}</td> 
   <td>a,ab,abc</td> 
   <td>a,ca,bca</td> 
  </tr> 
 </tbody> 
</table>

#### next 数组 (子串回溯的位置) ####

![8d828655107aef112054c6726e95310d.png][]

*  匹配的过程 KMP 算法的过程
    
    ***移动主串情况***
    
    1.  如果是 j== -1 ,表示就是第一个字符匹配失败，第一个元素匹配失败，不需要移动子串，只需要移动主串
    2.  或者 字符串匹配成功
    
    ![a5000117654e51b65c2f8532e3ec02c2.png][]

![da072d225075c150ac60138aef195aa6.png][]

***不移动主串的情况***

1.  匹配失败，子串回溯
2.  右移的数字 = 已经匹配的字符数-对应的部分匹配值 j=next\[j\]+1

#### 代码 ####

int kmp(char str[],char temp[])//这个是查找
    {
     
    	int i = 0;//这个是主字符串的位置
    	int j = 0;//这个是子字符串的位置
    	int length1 = strlen(str);
    	int length2 = strlen(temp);
    	while (i<length1&&j<length2) 
    	{
    		if (j==-1||str[i] == temp[j]) {
    			i++;
    			j++;
    		}
    		else {
    			j = next[j];
    		}
    	}
    	if (j==length2) {
    		return  i - j;
    	}
    	return  -1;
    	
    }

*  代码 next 数组怎么求

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    int next[1001];//这个是next数组
    //函数声明
    void getNext(char str[]);
    int KMP(char str[],char temp[]);
    int main()
    {
    	int i = 0;
    	char str[1001];//这个是主字符串
    	char temp[1001];//这个是用来匹配的字符串
    	int length = 0;//这个是主字符串的长度。
    	int result = -1;
     
    	printf("请输入第一个字符串\n");
    	gets(str);//在vs中用scanf_s();
    	printf("请输入第二个字符串\n");
    	gets(temp);//在vs中用scanf_s();
     
    	getNext(str);//建立next数组
     
    	result = KMP(str,temp);//这个是获取结果
     
            printf("\n");
     
    	if (result <= 0) {
    		printf("没有找到匹配的字符串");
    	}
    	else {
    		printf("结果在主字符串的位置为 %d",result+1);
    	}
    	// system("pause");
    	return  0;
    }
    void getNext(char str[])//next数组的建立，这个是关键
    {
        // 初始化
    	int i=0,j = -1;
    	int length1 = strlen(str);
        // 第一个不匹配的话，是主串开始往后加一
    	next[0] = -1;
    	
    	while (i < length1) {
    
            // -1 表示是第一个字符串，第一个字符串不需要赋值，因为肯定是-1 ,
            // 还有一种情况就是
    		if ( j== -1 || str[j] == str[i]) {
    			i++;
    			j++;
                
    			next[i] = j;
     
    		}
    		else {
    			j = next[j];
    		}
    	}
    }
    int kmp(char str[],char temp[])//这个是查找
    {
     
    	int i = 0;//这个是主字符串的位置
    	int j = 0;//这个是子字符串的位置
    	int length1 = strlen(str);
    	int length2 = strlen(temp);
    	while (i<length1&&j<length2) 
    	{
    		if (j==-1||str[i] == temp[j]) {
    			i++;
    			j++;
    		}
    		else {
    			j = next[j];
    		}
    	}
    	if (j==length2) {
    		return  i - j;
    	}
    	return  -1;
    }

[6fbf00f2a856d55f6769b38352d1146f.png]: /images/20221120/a9b57ba0309a40db8dac310e824d8af1.png
[c246cfa0bace7adde6ea58d47d317ebd.png]: /images/20221120/72ed69ab4c1d46f38a992ad864b21d4d.png
[eecf73237e14166b68662ef5f2c4c680.png]: /images/20221120/a835e8030c894414afd7b23d6dd4681a.png
[bb91d4c19da6787cf123509c05fceb59.png]: /images/20221120/01ee87d66edc48ad8c2e599fd54ff3b4.png
[8d828655107aef112054c6726e95310d.png]: /images/20221120/227cd3d4056e44c991ecc5380300b745.png
[a5000117654e51b65c2f8532e3ec02c2.png]: /images/20221120/9e77518e3a7e455eb50b3687614e06a6.png
[da072d225075c150ac60138aef195aa6.png]: /images/20221120/8d22444f839f41b899a17e3b5160635f.png