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

更新日期：September 26th 2020, 9:24:38 am

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

CATALOG
  1. 1. How to calc the next array.
Total : 89
2021
2020
2019
2018
2017
2016
illegal 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 网络安全 castby story cocos cocos2dx game selector classLoader findClass java 八皇后 english funnny blob bomb exploding git memory tree algorithm php5 wifi ftp service Go exception hexo blog CI/CD github actions http 编码 Queue Stack FrontDesign Chrome Plugins Sprider Basic knowledge js language parser Lock Tricks Cheat Sheet Javassist JVM Class file Memory jvm K8s Deployment kali 渗透 firewall firewalld iptables protocol strategy Database firstSet FollowSet ll1 table acm ANSI ASCII decode encode ISO-8859-1 messy code injection mysqli php sql注入 Sql optimization Mysql index B + tree InnoDB IO exploit NSA atom expression lanauage operator parse precedence phpstorm xampp xdebug 环境配置 apache security web server pickle 序列化 Message Queue Notes redis string note Redis Middleware Cache 撤销 数据结构 match regex test tutorial Linux Extension gcd rsa call-back Request scrapy spider 爬虫 qzone selenium webdriver black box lisp module scheme sicp case condition hanoi recursion Architecture Sql Optimize Explain 策略模式 设计模式 后缀表达式 symbol Network TCP Web Program Idea Thread concurrency u盘 病毒 csrf login session token uid web xss Story effective tools win10 windows
Security Design Java Algorithm FrontPage Linux Python Story Cocos BackStage Go FrontDesign Spider Parser-amp-language JVM K8s JVM/Java Database Mysql Java/Network Mysql/Database Java/Network/IO Algorithm/Bit-operation Java/Middleware Redis Front Redis/Cache Architecture Mysql/Sql Network Idea System