数据结构】图解KMP模式匹配算法（C语言）

你的名字 2023-02-16 15:26 15阅读 0赞

### 文章目录 ###

*   *  介绍
     *  KMP模式匹配原理
     *  next数组值推导
     *  KMP模式匹配算法实现
     *  KMP模式匹配改进
     *  nextval数值推导
     *  测试代码

## 介绍 ##

KMP算法是有Kunth和Partt共同研究，Morris独立研究发表的模式匹配算法，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。

## KMP模式匹配原理 ##

从朴素模式匹配的角度理解KMP模式匹配

假设主串S=“abcdefgab”，子串 T=“abcdex”，如果用朴素算法的话，前5个字母，两个串完全相等，直到第六个字母，“f”与“x”不相等。如下图所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]

图1-1  
接下来，按照朴素模式匹配，应该是图1-1的流程23456。即主串S中当i=2,3,4,5,6时，首字符与子串T的首字符均不等。

认真观察发现，对于要匹配的子串T来说，“abcdex”首字母“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与后面的子串任一字符相等，那么对于图1-1的1来说，前五位字符分别相等，意味着子串T的首字符“a”不可能与S串的第二位到第五位的字符相等。图1-1中的2,3,4,5判断都是多余。  
这是理解KMP算法的关键。如果我们知道T串中首字符“a”与T后面的字符均不相等，（注意这是前提）。而T串的第二位的“b”与“s”串中的第二位b在图1-1中的1中已经判断是相等的，那么也就意味着，T串中首字符“a”与S串中的第二位“b”是不需要判断也知道他们是不可能相等，这样图1-1中的2步骤是可以省略的。如图1-2所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 1]

图1-2

同样的道理，在我们知道T串中首字符“a”与T中后面的字符均不相等的前提下，T串的“a”与S串后面的cde也可以在步骤1之后可以确定是不相等的，所以这个算法中步骤2,3,4,5没有必要，只保留步骤1,6即可。如图1-3  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 2]

图1-3

之所以保留步骤6是因为步骤6中的判断是因为在步骤1中T\[6\]不等于S\[6\],尽管 我们已经知道了T\[1\]不等于T\[6\],但是也不能判断T\[1\]一定不等于S\[6\]。  
那么问题来了，如果T串后面也含有首字符“a”的字符怎么办？  
我们举一个例子，假设S=“abcabcabc”，T=“abcabx”，对于开始的判断，前五个字符完全相等，前6个字符不相等，如图1-4中的①。此时根据刚才的经验，T的首字符“a”与T的第二个字符“b”，第三位“c”均不等，所以不需要做判断，图1-4中的朴素算法②③都是多余的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 3]

图1-4  因为T的首位“a”与T的第四位的“a”相等，第二位的“b”与第五位的“b”相等，而在①时，第四位的“a”与第五位的“b”已经与主串S中的相应位置比较多了，是相等的，因此可以断定，T的首字符“a”，第二位字符“b”与与S的第四位和第五位也不需要比较了，肯定也是相等，所以说步骤④⑤也可省略。

也就是说，对于在子串中有首字符相等的字符，也是可以省略一部分不必要的判断步骤，如图1-5所示。省略掉右图的T串前两位“a”与“b”同S串的4,5位置字符匹配操作。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 4]

图1-5

对比这两个例子，我们会发现在①时，我们的i值，也就是主串当前位置的下标是6，②③④⑤，i值是2,3,4,5，到了⑥，i值才回到了6.即我们在朴素模式匹配算法汇总，主串的i值是不断的回溯来完成的。而我们分析发现，这种回溯其实是可以不需要的——KMP算法就是为了让这没有必要的回溯不发生。  
既然i值不回溯，也就是不可以变小，那么要考虑的变化就是j值了。通过观察也可以发现，我们屡屡提到了T串的首字符与自身后面字符的比较，发现如果有相等字符，j值的变化就会不相同。也就是说，这个j值的变化与主串没有什么关系，关键取决于T串的结构中是否有重复的问题。

我们把T串各个位置j值变化定义为一个数组next，那么next的长度就是T串的长度，得到函数定义：  
![在这里插入图片描述][20200610201511903.png]

## next数组值推导 ##

如何具体推导出一个串的next数值了？  
举一个栗子  
T=abcdex。  
![在这里插入图片描述][20200610213459761.png]  
当j=1时，next\[1\]=1。  
当j=2时，就由1到j-1就只有一个字符“a”，属于其他情况next\[2\]=1。  
当j=3时，j由1到j-1串是“ab”，显然a与b不相等，属于其他情况，next\[3\]=1。  
以后同理，所以最终T串的next\[j\]为011111。

T=abcabc。  
![在这里插入图片描述][20200610215002321.png]j=1时，next\[1\]=0;  
j=2时，同上例，next\[2\]=1;  
j=3时，同上next\[3\]=1;  
j=4时，同上next\[4\]=1  
j=5时，此时j由1到j-1的串是“abca”，前缀字符a与后缀a相等，因此可以退出k值为2，next\[5\]=2;  
j=6时，j由1到j-1的串是abcab，由于前缀字符“ab”与后缀“ab”相等，所以next\[6\]=3

**根据经验得到如果一个前后缀一个字符相等，k值是2，两个字符k值是3，n个相等k值就是n+1**

T=ababaaaba  
![在这里插入图片描述][20200610221501429.png]  
j=1时，next\[1\]=0;  
j=2时，同上next\[2\]=1;  
j=3时，next\[3\]=1  
j=4时，j由1到j-1的串aba，前缀字符a与后缀字符a相等next\[4\]=2  
j=5时，j由1到j-1的串是abab，由于前缀字符ab与后缀字符ab相等，所有next\[5\]=3;  
j=6时，j由1到j-1的串是ababba由于前缀字符aba与后缀aba相等，所以next\[6\]=4;  
j=7时，j由1到j-1的串是ababaa，由于前缀字符ab与后缀aa并不相等，只有a相等，所以next\[7\]=2；  
j=8时，j由1到j-1的串是ababaaa，只有a相等，所以next\[8\]=2  
j=9时，j由1到j-1的串是ababaaab，由于前缀字符ab与后缀ab相等，所以next\[9\]=3.

## KMP模式匹配算法实现 ##

/* 通过计算返回子串T的next数组。 */
    void get_next(String T, int *next) 
    {
        
    	int i,j;
      	i=1;
      	j=0;
      	next[1]=0;
      	while (i<T[0])  /* 此处T[0]表示串T的长度 */
     	{
        
        	if(j==0 || T[i]== T[j]) 	
        	/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
    		{
        
          		++i;  
    			++j;  
    			next[i] = j;
        	} 
    		else 
    			j= next[j];	/* 若字符不相同，则j值回溯 */
      	}
    }

这段代码就是Wie了计算出当前要匹配的串T的next函数。

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。 */
    /*  T非空，1≤pos≤StrLength(S)。 */
    int Index_KMP(String S, String T, int pos) 
    {
        
    	/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
    	int i = pos;		
    	/* j用于子串T中当前位置下标值 */
    	int j = 1;		
    	/* 定义一next数组 */	
    	int next[255];		
    	/* 对串T作分析，得到next数组 */
    	get_next(T, next);	
    	/* 若i小于S的长度并且j小于T的长度时，循环继续 */
    	while (i <= S[0] && j <= T[0]) 
    	{
        
    		/* 两字母相等则继续，与朴素算法增加了j=0判断 */
    		if (j==0 || S[i] == T[j]) 	
          	{
        
             	++i;
             	++j; 
          	} 
          	else 			
          		/* 指针后退重新开始匹配 */
          		/* j退回合适的位置，i值不变 */
          	 	j = next[j];
    	}
    	if (j > T[0]) 
    		return i-T[0];
    	else 
    		return 0;
    }

## KMP模式匹配改进 ##

后来有人发现，KMP还是有缺陷的，比如，我们的主串S=aaaabcde，子串T=aaaax，其next数值分别为123456，在开始时，i=5，j=5时，我们发现b与a不相等，如图1-6中的①，因此j=next\[5\]=4,如图中的②，此时b与第四位置的a依然不等，j=next\[4\]=3,如入栈的③，后依次是④⑤，直到j=next\[1\]=0时，根据算法，此时i++，j++得到i=6，j=1，如图中⑥。  
.![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 5]

图1-6  我们发现当中的②③④⑤，其实是多余的判断，由于T串的第二三四五位置的字符都与首位的a相等，那么可以用收的next\[1\]的值其取代与他相等的字符后续next\[j\]的值。

/* 求模式串T的next函数修正值并存入数组nextval */
    void get_nextval(String T, int *nextval) 
    {
        
      	int i,j;
      	i=1;
      	j=0;
      	nextval[1]=0;
      	  /* 此处T[0]表示串T的长度 */
      	while (i<T[0])
     	{
        
     		/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
        	if(j==0 || T[i]== T[j]) 	
    		{
        
          		++i;  
    			++j;  
    			  /* 若当前字符与前缀字符不同 */
    			if (T[i]!=T[j])   
    				/* 则当前的j为nextval在i位置的值 */ 
    				nextval[i] = j;	
          		else 
          		/* 如果与前缀字符相同，则将前缀字符的 */
    			/* nextval值赋值给nextval在i位置的值 */
    				nextval[i] = nextval[j];	
        	} 
    		else 
    			/* 若字符不相同，则j值回溯 */
    			j= nextval[j];		
      	}
    }

## nextval数值推导 ##

T=ababaaaba  
![在这里插入图片描述][20200610224457699.png]  
先算法next数组的值分别非001234223，然后在判断。  
j=1时，nextval=0；  
j=2时，因为第二位字符b的next值是1，而第一位是a他们不相等，所以nextval\[2\]=next\[2\]=1.  
j=3时，因为第三位字符a的next值为1，所以第一位的a比较得知他们相等，所以nextval\[3\]=nextval\[1\]=0。  
![在这里插入图片描述][20200610224851774.png]  
j=4时，第四位的字符bnext值为2所以第二位的b相比较得结果是相等的，因此nextval\[4\]=nextval\[2\]=1.  
![在这里插入图片描述][20200610225042818.png]  
j=5时，next值为3，第五个字符a与第三个字符a相等，因此nextval\[5\]=nextval\[3\]=0  
j=6时，next值为4，第六个字符a与第四个字符b不相等，因此nextval\[4\]=4  
j=7时，next值为2，第七个字符a与第二个字符b不相等，因此nextval\[7\]=2  
j=8时，next值为2，第八个字符b与第三个字符b相等，因此nextval\[8\]=nextval\[2\]=1  
j=9时，next值为3，第八个字符b与第三个字符a相等，因此nextval\[9\]=nextval\[3\]=1.

## 测试代码 ##

#include "string.h"
    #include "stdio.h"    
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 100 /* 存储空间初始分配量 */
    
    typedef int Status;		/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    typedef int ElemType;	/* ElemType类型根据实际情况而定，这里假设为int */
    
    typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */
    
    /* 生成一个其值等于chars的串T */
    Status StrAssign(String T,char *chars)
    {
         
    	int i;
    	if(strlen(chars)>MAXSIZE)
    		return ERROR;
    	else
    	{
        
    		T[0]=strlen(chars);
    		for(i=1;i<=T[0];i++)
    			T[i]=*(chars+i-1);
    		return OK;
    	}
    }
    
    Status ClearString(String S)
    {
         
    	S[0]=0;/*  令串长为零 */
    	return OK;
    }
    
    /*  输出字符串T。 */
    void StrPrint(String T)
    {
         
    	int i;
    	for(i=1;i<=T[0];i++)
    		printf("%c",T[i]);
    	printf("\n");
    }
    
    /*  输出Next数组值。 */
    void NextPrint(int next[],int length)
    {
         
    	int i;
    	for(i=1;i<=length;i++)
    		printf("%d",next[i]);
    	printf("\n");
    }
    
    /* 返回串的元素个数 */
    int StrLength(String S)
    {
         
    	return S[0];
    }
    
    /* 朴素的模式匹配法 */
    int Index(String S, String T, int pos) 
    {
        
    	int i = pos;	/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
    	int j = 1;				/* j用于子串T中当前位置下标值 */
    	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
    	{
        
    		if (S[i] == T[j]) 	/* 两字母相等则继续 */
          	{
        
    			++i;
             	++j; 
          	} 
          	else 				/* 指针后退重新开始匹配 */
          	{
          
             	i = i-j+2;		/* i退回到上次匹配首位的下一位 */
             	j = 1; 			/* j退回到子串T的首位 */
          	}      
    	}
    	if (j > T[0]) 
    		return i-T[0];
    	else 
    		return 0;
    }
    
    /* 通过计算返回子串T的next数组。 */
    void get_next(String T, int *next) 
    {
        
    	int i,j;
      	i=1;
      	j=0;
      	next[1]=0;
      	while (i<T[0])  /* 此处T[0]表示串T的长度 */
     	{
        
        	if(j==0 || T[i]== T[j]) 	/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
    		{
        
          		++i;  
    			++j;  
    			next[i] = j;
        	} 
    		else 
    			j= next[j];	/* 若字符不相同，则j值回溯 */
      	}
    }
    
    /* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。 */
    /*  T非空，1≤pos≤StrLength(S)。 */
    int Index_KMP(String S, String T, int pos) 
    {
        
    	int i = pos;		/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
    	int j = 1;			/* j用于子串T中当前位置下标值 */
    	int next[255];		/* 定义一next数组 */
    	get_next(T, next);	/* 对串T作分析，得到next数组 */
    	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
    	{
        
    		if (j==0 || S[i] == T[j]) 	/* 两字母相等则继续，与朴素算法增加了j=0判断 */
          	{
        
             	++i;
             	++j; 
          	} 
          	else 			/* 指针后退重新开始匹配 */
          	 	j = next[j];/* j退回合适的位置，i值不变 */
    	}
    	if (j > T[0]) 
    		return i-T[0];
    	else 
    		return 0;
    }
    
    /* 求模式串T的next函数修正值并存入数组nextval */
    void get_nextval(String T, int *nextval) 
    {
        
      	int i,j;
      	i=1;
      	j=0;
      	nextval[1]=0;
      	while (i<T[0])  /* 此处T[0]表示串T的长度 */
     	{
        
        	if(j==0 || T[i]== T[j]) 	/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
    		{
        
          		++i;  
    			++j;  
    			if (T[i]!=T[j])      /* 若当前字符与前缀字符不同 */
    				nextval[i] = j;	/* 则当前的j为nextval在i位置的值 */
          		else 
    				nextval[i] = nextval[j];	/* 如果与前缀字符相同，则将前缀字符的 */
    											/* nextval值赋值给nextval在i位置的值 */
        	} 
    		else 
    			j= nextval[j];			/* 若字符不相同，则j值回溯 */
      	}
    }
    
    int Index_KMP1(String S, String T, int pos) 
    {
        
    	int i = pos;		/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
    	int j = 1;			/* j用于子串T中当前位置下标值 */
    	int next[255];		/* 定义一next数组 */
    	get_nextval(T, next);	/* 对串T作分析，得到next数组 */
    	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
    	{
        
    		if (j==0 || S[i] == T[j]) 	/* 两字母相等则继续，与朴素算法增加了j=0判断 */
          	{
        
             	++i;
             	++j; 
          	} 
          	else 			/* 指针后退重新开始匹配 */
          	 	j = next[j];/* j退回合适的位置，i值不变 */
    	}
    	if (j > T[0]) 
    		return i-T[0];
    	else 
    		return 0;
    }
    
    int main()
    {
        
    	int i,*p;
    	String s1,s2;
    	
    	StrAssign(s1,"abcdex");
    	printf("子串为: ");
    	StrPrint(s1);
    	i=StrLength(s1);
    	p=(int*)malloc((i+1)*sizeof(int));
    	get_next(s1,p); 
    	printf("Next为: ");
    	NextPrint(p,StrLength(s1));
    	printf("\n");
    
    	StrAssign(s1,"abcabx");
    	printf("子串为: ");
    	StrPrint(s1);
    	i=StrLength(s1);
    	p=(int*)malloc((i+1)*sizeof(int));
    	get_next(s1,p); 
    	printf("Next为: ");
    	NextPrint(p,StrLength(s1));
    	printf("\n");
    
    	StrAssign(s1,"ababaaaba");
    	printf("子串为: ");
    	StrPrint(s1);
    	i=StrLength(s1);
    	p=(int*)malloc((i+1)*sizeof(int));
    	get_next(s1,p); 
    	printf("Next为: ");
    	NextPrint(p,StrLength(s1));
    	printf("\n");
    
    	StrAssign(s1,"aaaaaaaab");
    	printf("子串为: ");
    	StrPrint(s1);
    	i=StrLength(s1);
    	p=(int*)malloc((i+1)*sizeof(int));
    	get_next(s1,p); 
    	printf("Next为: ");
    	NextPrint(p,StrLength(s1));
    	printf("\n");
    
    	StrAssign(s1,"ababaaaba");
    	printf("   子串为: ");
    	StrPrint(s1);
    	i=StrLength(s1);
    	p=(int*)malloc((i+1)*sizeof(int));
    	get_next(s1,p); 
    	printf("   Next为: ");
    	NextPrint(p,StrLength(s1));
    	get_nextval(s1,p); 
    	printf("NextVal为: ");
    	NextPrint(p,StrLength(s1));
    	printf("\n");
    
    	StrAssign(s1,"aaaaaaaab");
    	printf("   子串为: ");
    	StrPrint(s1);
    	i=StrLength(s1);
    	p=(int*)malloc((i+1)*sizeof(int));
    	get_next(s1,p); 
    	printf("   Next为: ");
    	NextPrint(p,StrLength(s1));
    	get_nextval(s1,p); 
    	printf("NextVal为: ");
    	NextPrint(p,StrLength(s1));
    
    	printf("\n");
    
    	StrAssign(s1,"00000000000000000000000000000000000000000000000001");
    	printf("主串为: ");
    	StrPrint(s1);
    	StrAssign(s2,"0000000001");
    	printf("子串为: ");
    	StrPrint(s2);
    	printf("\n");
    	printf("主串和子串在第%d个字符处首次匹配（朴素模式匹配算法）\n",Index(s1,s2,1));
    	printf("主串和子串在第%d个字符处首次匹配（KMP算法） \n",Index_KMP(s1,s2,1));
    	printf("主串和子串在第%d个字符处首次匹配（KMP改良算法） \n",Index_KMP1(s1,s2,1));
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610124758284.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200610130020996.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200610130338313.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200610174353758.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200610192050295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70
[20200610201511903.png]: https://img-blog.csdnimg.cn/20200610201511903.png
[20200610213459761.png]: https://img-blog.csdnimg.cn/20200610213459761.png
[20200610215002321.png]: https://img-blog.csdnimg.cn/20200610215002321.png
[20200610221501429.png]: https://img-blog.csdnimg.cn/20200610221501429.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200610223600797.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70
[20200610224457699.png]: https://img-blog.csdnimg.cn/20200610224457699.png
[20200610224851774.png]: https://img-blog.csdnimg.cn/20200610224851774.png
[20200610225042818.png]: https://img-blog.csdnimg.cn/20200610225042818.png