写了个next数组

末蓝、 2021-12-20 14:09 241阅读 0赞

一直很纠结，上个月那次群赛，一直没有a掉拿到字符串匹配的题目。早上空气好，起来自己再写了一下那个KMP的next数组。

推荐看一篇博文，里面写得很清楚next数组的产生：[http://www.matrix67.com/blog/archives/115][http_www.matrix67.com_blog_archives_115]

贴上代码留作纪念吧

\#include  < iostream >   
\#include  < cstring >   
 using   namespace  std;  
  
 // 这个next函数，所有的数组，字符串，下标都是从1开始计数的   
 void  GetNext( char   \* T,  int  n,  int   \* next)  
\{  
     for ( int  i  =   0 ; i  <  n; i \++ )  
        next\[i\]  =   0 ;  
  
    next\[ 1 \]  =   0 ;  
     int  j  =   0 , i  =   2 ;  
     for ( int  i  =   2 ; i  <  n; i \++ )      
    \{  
         while (j > 0   &&  T\[j \+ 1 \]  !=  T\[i\]) j  =  next\[j\];  
         if (T\[j \+ 1 \]  ==  T\[i\]) j  \+=   1 ;  
        next\[i\]  =  j;          
    \}  
     /\*   
    在此处总结一下：事实上，T\[next\[i\]\] == T\[i\]的,最初要得到next\[i\]是  
    通过这个规则来计算：  
    next\[j\]应该是所有满足T\[1..next\[j\]\] == T\[j-next\[j\]+1..j\]的最大值。  
     \*/   
\}

转载于:https://www.cnblogs.com/ktyanny/archive/2010/04/09/1708056.html

[http_www.matrix67.com_blog_archives_115]: http://www.matrix67.com/blog/archives/115

发表评论取消回复

表情：

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

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

相关阅读

相关 KMP算法的Next数组详解

目录 KMP算法的Next数组详解引开始优化 KMP算法的Next数组详解转载请注明[来源][Lin

r囧r小猫/ 2023年06月01日 06:11/ 0 赞/ 26 阅读

相关 KMP算法next数组中k = next[k]

KMP算法next数组中k = next\[k\] next数组是KMP算法的关键，用于储存模式串指针j回溯的值，当模式串与主串失配时，利用next数组更快地找到模式串下

「爱情、让人受尽委屈。」/ 2023年02月10日 12:28/ 0 赞/ 45 阅读

相关 KMP next 数组讲解

文章目录 KMP next 数组讲解 C 语言版本代码： KMP next 数组讲解 > 重点在于匹配不上回退的理解 !

Love The Way You Lie/ 2023年01月01日 05:59/ 0 赞/ 153 阅读

相关 kmp算法：next数组解

kmp算法小白式学法不需要指针回溯，并实现自由的主串，先直接上代码 ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_5

ゝ一世哀愁。/ 2022年12月17日 15:56/ 0 赞/ 178 阅读

相关尴尬，写了个死循环

突然群里有人说接口有问题了，查看日志是调用一个第三方接口被限流了，然后找合作方增加了限流配额。合作方说有个接口的调用已经达到百万次了，通过查看日志，发现程序进入了死循环。下

忘是亡心i/ 2022年10月02日 01:47/ 0 赞/ 172 阅读

相关 KMP算法的next[]数组通俗解释

我们在一个母字符串中查找一个子字符串有很多方法。KMP是一种最常见的改进算法，它可以在匹配过程中失配的情况下，有效地多往后面跳几个字符，加快匹配速度。当然我们可以看到这个算

柔情只为你懂/ 2022年08月21日 10:40/ 0 赞/ 191 阅读

相关 next数组介绍

首先看看next数组值的求解方法例如：模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2

比眉伴天荒/ 2022年08月05日 10:27/ 0 赞/ 184 阅读

相关 KMP算法计算next数组匹配字符串

1.概念 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称

朴灿烈づ我的快乐病毒、/ 2022年06月15日 02:48/ 0 赞/ 229 阅读

相关 KMP入门级别算法详解--终于解决了（next数组详解）

对于正常的字符串模式匹配，主串长度为m，子串为n，时间复杂度会到达O（m\n），而如果用KMP算法，复杂度将会减少线型时间O（m+n）。设主串为ptr="ababaa

Dear 丶/ 2022年06月10日 10:25/ 0 赞/ 202 阅读

相关写了个next数组

　　　　一直很纠结，上个月那次群赛，一直没有a掉拿到字符串匹配的题目。早上空气好，起来自己再写了一下那个KMP的next数组。　　推荐看一篇博文，里面写得很清楚next

末蓝、/ 2021年12月20日 14:09/ 0 赞/ 242 阅读