ReZero's Utopia.

KMP

Algorithm KMP
Word count: 126Reading time: 1 min
2019/09/18 Share

How to calc the next array.

  1. Calc the max length of suffix and prefix as follows:

    string a b a a b c a b a
    length 0 0 1 1 2 0 1 2 3
    next -1 0 0 1 1 2 0 1 2

    As you can see, the next array is the suffix equals prefix length array move on one step and init the first values as -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
void GetNext(char* p,int next[])  
  {  
      next[0] = -1;  
      int k = -1,  = 0;  
      while (j < (p.length - 1)) {  
          //p[k]表示前缀，p[j]表示后缀  
          if (k == -1 || p[j] == p[k]) {  
              ++j, ++k, next[j] = k;  
          } else {  
              k = next[k];  
          }  
      }  
  }

Author：ReZero

原文链接：https://rezeros.github.io/2019/09/18/KMP/

发表日期：September 18th 2019, 5:31:00 pm

更新日期：July 5th 2020, 2:47:05 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. How to calc the next array.
Total : 103
2020
2019
2018
2017
2016
Story Algorithm bits Math Queue Stack Java Debug JDWP KMP 3d animation css javascript android 库 索引 permission 正则 domain kali scan-tools security sub-domain arch bbr google linux network speed tcp archlinux gdm shell themes cdn ip 网络安全 castby story selector classLoader findClass java 八皇后 html 标签 python 凯撒密码 击鼓传花 数据结构 算法 数据结构与算法 编码 android studio 布局 思维导图 algorithm csrf login session token uid web xss spider 嗅事百科 join 优化 电话 编程 illegal 拓扑排序 课程安排 gcd rsa 二叉树 有序树 正则表达式 后缀表达式 apache web server 渗透 cocos cocos2dx game match regex test tutorial 数据 english funnny blob bomb exploding git memory tree php5 wifi ftp service http-equiv http协议 http FrontDesign Chrome Plugins Sprider Basic knowledge js language parser note Javassist jsp jvm scan tools firewall firewalld iptables protocol strategy Database firstSet FollowSet ll1 table acm ANSI ASCII decode encode ISO-8859-1 messy code msfconsole injection mysqli php sql注入 Mybatis exploit NSA atom expression lanauage operator parse precedence 安全 序列化与反序列化 微信 phpstorm xampp xdebug 环境配置 PIL pickle 序列化 Message Queue Notes redis string 撤销 K8s Linux Extension call-back Request scrapy 爬虫 qzone selenium webdriver black box lisp module scheme sicp case condition hanoi recursion baidu tieba Sql Optimize Explain 策略模式 设计模式 symbol u盘 病毒 webshell effective win10 windows hexo blog CI/CD github actions
Design Story Algorithm Java FrontPage Android Security Linux BackStage Python Algorithm/Bit-operation Cocos FrontDesign Spider Parser-amp-language Database Java/Backstage Regex Java/Middleware K8s Front Mysql Mysql/Sql