[串] KMP算法（考试记忆版）

小鱼儿 2024-04-20 08:12 60阅读 0赞

##### KMP代码 #####

1.  KMP匹配

// KMP搜索：下标0处存长度
    int KMP(char *str, char *substr, int next[]) { 
    	int i=1,j=1;
    	while (i<=str[0] && j<=substr[0]) { 
    		if (j==0 || str[i]==substr[j]) { 
    			++i;++j;
    		} else { 
    			j = next[j]; //失配，回溯
    		}
    	}
    	if (j>substr[0])  return i-substr[0]; //匹配成功
    	else: return 0; //匹配失败
    }

1.  求next数组

// T[0]存着字符串长度
    void getnext(char *T, int next[]) { 
    	int j=1,t=0;
    	next[1] = 0; //特殊状态
    	while (j<T[0]) {  //已知next[j]求next[j+1]，所以j不能等于T[0]
    		if (t==0 || T[j]==T[t]) { 
    			next[j+1] = t+1;
    			++j;++t;
    		}
    		else t = next[t];
    	}
    }

1.  求nextval数组

【第一种】在求next数组的算法中修改部分逻辑，即可求nextval数组

// 在求next数组的过程中，求nextval数组
    void getnextval(char *T, int next[], int nextval[]) { 
    	int j=1, t=0;
    	next[1] = 0;
    	nextval[1]=0; //特殊情况
    	while (j<T[0]) {  //已知next[j]，求得next[j+1] --> 再依据next[j+1]，求得nextval[j+1]
    		if (t==0 || T[j]==T[t]) {  //匹配成功
    			next[j+1] = t+1; //求得next[j+1]
    			// 求nextval[j+1]
    			if ( T[j+1] != T[ next[j+1] ] ) nextval[j+1] = next[j+1];
    			else nextval[j+1] = nextval[ next[j+1] ];
    			++j;++t;
    		}
    		else t = nextval[t];
    	}
    }

【第二种】由模式串直接求得nextval数组

// 由模式串T求nextval数组
    void getnextval(char *T, int nextval[]) { 
    	int j=1, t=0;
    	nextval[1] = 0; //初始情况
    	while (j < T[0]) {  //已知nextval[j]，求next[j+1]
    		if (t==0 || T[j]==T[t]) { 
    			if (T[j+1]!=T[t+1]) nextval[j+1] = t+1;
    			else nextval[j+1] = nextval[t+1];
    			++j; ++t;
    		}
    		else t = nextval[t];
    	}
    }

##### KMP手算 #####

【例题】模式串"ababaaababaa"，求nextval数组（下标从1开始，0记录长度）

【先求next数组】

1.  先画出表格（下标、T、next），并赋值特殊情况next\[1\]=0
2.  看下标`j`那列，记下前面的子串T\[1\]-T\[j-1\]，找出最长的前后缀
    
    1.  没有相同的前后缀 --> next\[j\] = 1
    2.  有相同的前后缀 --> 取最长的前后缀，长度为len --> next\[j\]=len+1

【再求nextval数组】

1.  画出nextval行，并赋值特殊情况nextval\[1\]=0
2.  【算法：求单元格(j, nextval)】先锁定下标为j的那一列 --> 然后看第j列，next那一行（j, next）的值t --> 然后看第t列，T那一行（t, T）–> 用(t, T)和(j, T)比较
    
    1.  (t, T)==(j, T) 的话：(j, nextval)=(t, nextval)
    2.  (t, T)≠(j, T)的话：(j, nextval)=(j, next)
3.  【举例：求单元格(5,nextval)】锁定下标为5的那一列 --> (5, next)=3 --> (3, T)=a --> (3, T)=a与(5, T)=a比较 --> 相同，则(5, nextval)=(3, nextval)=3
4.  【举例：求单元格(6, nextval)】锁定下标为6的那一列 --> (6, next)=4 --> (4, T)=b --> (4, T)=b与(6, T)=a比较 --> 不同，则(6, nextval)=(6, next)

<table> 
 <thead> 
  <tr> 
   <th>下标</th> 
   <th>1</th> 
   <th>2</th> 
   <th>3</th> 
   <th>4</th> 
   <th>5</th> 
   <th>6</th> 
   <th>7</th> 
   <th>8</th> 
   <th>9</th> 
   <th>10</th> 
   <th>11</th> 
   <th>12</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>T</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>a</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>b</td> 
   <td>a</td> 
   <td>a</td> 
  </tr> 
  <tr> 
   <td>next</td> 
   <td>0</td> 
   <td>1</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>2</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>nextval</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>4</td> 
   <td>2</td> 
   <td>1</td> 
   <td>0</td> 
   <td>1</td> 
   <td>0</td> 
   <td>4</td> 
  </tr> 
 </tbody> 
</table>

【链接】[KMP全盘复习][KMP]

[KMP]: https://blog.csdn.net/summer_dew/article/details/82184347