KMP

电玩女神 2022-07-26 06:18 114阅读 0赞

（1）next\[0\]= -1 意义：任何串的第一个字符的模式值规定为-1。  
（2）next\[j\]= -1 意义：模式串T中下标为j的字符，如果与首字符  
相同，且j的前面的1—k个字符与开头的1—k  
个字符不等（或者相等但T\[k\]==T\[j\]）（1≤k<j）。

如：T=”abCabCad”

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>patten</td> 
   <td>a</td> 
   <td>b</td> 
   <td>C</td> 
   <td>a</td> 
   <td>b</td> 
   <td>C</td> 
   <td>a</td> 
   <td>d</td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>next</td> 
   <td>-1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>-1</td> 
   <td>0</td> 
   <td>0</td> 
   <td>-1</td> 
   <td>4</td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>index</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td>7</td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

则 next\[6\]=-1，因T\[3\]=T\[6\] .

（3）next\[j\]=k 意义：模式串T中下标为j的字符，如果j的前面k个  
字符与开头的k个字符相等，且T\[j\] != T\[k\] （1≤k<j）。  
即T\[0\]T\[1\]T\[2\]。。。T\[k-1\]==T\[j-k\]T\[j-k+1\]T\[j-k+2\]…T\[j-1\]  
且T\[j\] != T\[k\].（1≤k<j）;

(4) next\[j\]=0 意义：除（1）（2）（3）的其他情况。

发表评论取消回复

表情：

评论列表（有 0 条评论，114人围观）

还没有评论，来说两句吧...

相关阅读

相关 kmp算法和kmp的优化

一、kmp是什么 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简

以你之姓@/ 2023年07月13日 03:40/ 0 赞/ 3 阅读

相关 KMP

Kmp详解 [ 朴素匹配算法咱们先来看朴素匹配算法。假设现在文本串S匹配到 i 位置，模式串P匹

一时失言乱红尘/ 2022年08月10日 15:37/ 0 赞/ 116 阅读

相关 KMP

（1）next\[0\]= -1 意义：任何串的第一个字符的模式值规定为-1。（2）next\[j\]= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且

电玩女神/ 2022年07月26日 06:18/ 0 赞/ 115 阅读

相关 kmp

include <iostream> include <cstdio> include <string> include <cstring>

曾经终败给现在/ 2022年06月09日 07:51/ 0 赞/ 156 阅读

相关 KMP模板

1 include <iostream> 2 include <string> 3 using namespace std; 4 / P

╰+攻爆jí腚メ/ 2021年12月20日 23:57/ 0 赞/ 185 阅读

相关 Kmp算法

举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ ![bg2013050101.jpg][]

迷南。/ 2021年12月17日 11:13/ 0 赞/ 345 阅读

相关 KMP

KMP 输出版本二 include<bits/stdc++.h> using namespace std; const in

今天药忘吃喽~/ 2021年12月04日 07:49/ 0 赞/ 173 阅读

相关 KMP算法

一 KMP算法介绍 1 KMP是一个解决模式串在文本串是否出现过，如果出现过，求算出现的位置的经典算法。 2 Knuth-Morris-Pratt 字符串查找算法，简称

傷城~/ 2021年07月24日 18:29/ 0 赞/ 589 阅读

相关 kmp

如果s[i] != p[j+1] 时,令k=ne[j] ,k就是使最长前缀=后缀长度移动的最短距离由匹配数组ne的含义可知 p[1..k] = p[j-k+1

红太狼/ 2021年06月22日 15:37/ 0 赞/ 363 阅读

相关 KMP代码

#include <stdio.h> #include <string.h> char a[] = "abababaababacb"; char b[] = ...

朱雀/ 2021年03月28日 15:32/ 0 赞/ 519 阅读