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

更新日期：February 23rd 2021, 7:10:02 am

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

CATALOG
  1. 1. How to calc the next array.
Total : 95
2021
2020
2019
2018
2017
2016
AQS Java Concurrency 拓扑排序 数据结构与算法 课程安排 join 优化 电话 算法 编程 Algorithm HashMap Concurrent Hash Map Debug JDWP KMP 数据 Math Tips 3d animation css javascript arch bbr google linux network speed tcp archlinux gdm shell themes python 凯撒密码 cdn ip 网络安全 cocos cocos2dx game selector classLoader findClass java K8s Deployment 八皇后 Search engine english funnny blob bomb exploding git memory tree algorithm php5 wifi ftp service Go exception hexo blog CI/CD github actions 编码 Queue Stack FrontDesign Chrome Plugins Sprider Basic knowledge js language parser Lock Tricks Cheat Sheet Javassist JVM Class file Memory jvm kali 渗透 firewall firewalld iptables protocol strategy firstSet FollowSet ll1 table acm ANSI ASCII decode encode ISO-8859-1 messy code Sql optimization Database Mysql index B + tree InnoDB IO exploit NSA php phpstorm xampp xdebug 环境配置 apache security web server pickle 序列化 Message Queue Notes redis string note 撤销 数据结构 Linux Extension gcd rsa call-back Request scrapy spider 爬虫 qzone selenium webdriver black box lisp module scheme sicp case condition hanoi recursion Sql Mybatis Log Optimize Explain 策略模式 设计模式 后缀表达式 symbol Network TCP Web Thread concurrency u盘 病毒 csrf login session token uid web xss Story effective tools win10 windows castby story Program OS http Disk Deploy Redis Middleware Cache Architecture Idea atom expression lanauage operator parse precedence match regex test tutorial
Security Java Algorithm FrontPage Linux Python Cocos BackStage K8s java Story Go FrontDesign Spider Parser-amp-language Design JVM JVM/Java Mysql Database Mysql/Database Java/Network Algorithm/Bit-operation Java/Network/IO Java/Middleware Front Mysql/Sql Network System OS Redis Architecture Idea Redis/Cache