精华内容
下载资源
问答
  • next函数

    千次阅读 2018-03-09 08:51:00
    Next函数:指当子串与母串在子串第j个字符(母串第i个字符)时出现了不匹配。如果不让母串指针i回溯,只让子串指针j回溯,此时i指针指向的母串字符应该与子串中第next[j]个字符进行匹配。因此next[j]就是当子母串不...

    Next函数讲解:

     

    Next函数:指当子串与母串在子串第j个字符(母串第i个字符)时出现了不匹配。如果不让母串指针i回溯,只让子串指针j回溯,此时i指针指向的母串字符应该与子串中第next[j]个字符进行匹配。因此next[j]就是当子母串不匹配后,子串指针j会指向子串中第几个字符,而这里的第几个就是第j个。

    下面分情况讲解:

    当j=1时,即如果当j=1时字母就不匹配,此时指针j会指向子串中第几(next[j])个字符?我们知道前提是如果不匹配母串指针i是不变的还是指向不匹配的这个字符,因为子串的一个字符就不同所以从子串第i个字符开始的字符串指定与子串不匹配,又因为母串中第i个字符之前的字符都已经进行了匹配都不合格。所以子母串指针i与j都要往后移一位。子串中没有匹配的字符串所以记录该值为0,至于其他数行不行,我认为只要是非正数应该都可以,这里的0,只是个子母串不匹配的标志位。

    当子串第j个字符与母串第i个字符不匹配时,就要分情况了。

    如果子串除第j个字符外的前j-1个字符中,如果有以下这种情况,即子串前k-1个字符串与后k-1个字符串(后k-1个字符是到第j-1个字符而不是第j个字符)完全匹配则此时子串指针j就要回溯到子串中第k个字符与母串指针i指向的母串字符进行匹配判断。

    如果子串前j-i个字符中不满足,则子串指针j回溯到第1(即next[j]=1)个字符与母串指针指向的母串字符进行匹配判断。

    转载于:https://my.oschina.net/u/3782432/blog/1631986

    展开全文
  • KMP算法 next函数 代码解析

    千次阅读 2013-07-20 11:00:15
    KMP算法很早就接触了,记得自己看着代码也能理解实现,但是时间已久总是忘了如何编码,也许是自己对于next函数的理解一直停留在记忆层面上。 现在把KMP的next函数拿出来,看看能不能分析出一个门道,理解了它的逻辑...

    KMP算法很早就接触了,记得自己看着代码也能理解实现,但是时间已久总是忘了如何编码,也许是自己对于next函数的理解一直停留在记忆层面上。

    现在把KMP的next函数拿出来,看看能不能分析出一个门道,理解了它的逻辑,方式,才会记得比较熟悉吧。

    KMP的思想这里不探讨了,直接上next函数的代码来分析。


    void next(const char *T, int next[])
    {
           int j = 0, k = -1;//两个位置指针,j表示当前匹配指针。
    	   //j,k都代表了当前重复子串后的位置。即图(1)的F和D位置
           next[0] = -1;
    	   //把第一个的位置置为-1,表示从头开始匹配
           while ( T[j] != '\0' )//while循环
           {
                  if (k == -1 || T[j] == T[k])
                  {
                         ++j; ++k;
                         if (T[j]!=T[k])
                                next[j] = k;
                         else
                                next[j] = next[k];
                  }
                  else
                         k = next[k];
           }
    }


    个人理解,这个next函数有两个目的,1.求一个最长重复序列;2.根据最长序列求回溯位置。

    1.最长重复子序列:

    比如ABCDABC,这个序列的最长重复字序列式ABC,当然,这里的最长重复要满足要求,前一个顶头,后一个顶着尾巴。如下图(1)所示。
    CABCDABC,这个序列ABC子序列不满足前一个顶头的要求,所以这个序列的最长公共子序列是C。

    2.回溯位置。如图一,F之前的最长子序列求出来以后,我们目的是计算F的回溯位置。按照理解,我们匹配失败后,可以让F回溯到D的位置,因为它们的前缀是相同的。

    程序里还加了一个判断条件,就是继续还要判断F与D是否相等,如果相等,即都为F,那么F失败的时候回溯回来也是错误的,那么我们就然F指向D之前的位置。


    图(1)




    于是我们知道了程序的两个步骤,1,求最长子序列;2,求有效回溯位置(注意是有效);图(3)是程序的一个流程图:



    图(2)


    接下来,自己总结下next函数的思想。

    next是一种DP的思想,即动态规划。next和k指针都记录了以前计算的结果,next为前面元素匹配位置,k记录当前最长字串,用于后面的计算。其实我们也可以写一个简单寻找最长重复序列的非DP算法,不过那会很费时。

    展开全文
  • lua_next函数分析

    万次阅读 2015-08-16 15:54:07
    lua_next(L,index):先把 表(lua栈 index所指的表), 的当前索引弹出,再把table 当前索引的值弹出,也就是先弹出 table的索引,再弹出table索引的值 简单一个例子: NUMBER_TABLE_WITH_INDEX = { ["a"] = 1, ["b"]...

    lua_next(L,index):先把 表(lua栈 index所指的表), 的当前索引弹出,再把table 当前索引的值弹出,也就是先弹出 table的索引,再弹出table索引的值

    简单一个例子:

    <span style="font-family:KaiTi_GB2312;font-size:14px;">NUMBER_TABLE_WITH_INDEX =
    {
    ["a"] = 1,
    ["b"] = 2,
    ["c"] = 3
    }</span>

    <span style="font-family:KaiTi_GB2312;font-size:14px;"> lua_getglobal(L,"STRING_TABLE_WITH_INDEX");
        /*此时lua栈状态
        ----------------------------------
        |  -1 table NUMBER_TABLE
        ----------------------------------
        */</span>

     //循环遍历
        lua_pushnil(L);
        /*此时lua栈状态
        ----------------------------------
        |  -1 nil
        |  -2 table NUMBER_TABLE
        ----------------------------------
        */
        while(lua_next(L,-2))
        {
        /*此时lua栈状态
        ----------------------------------
        |  -1 value
        |  -2 key
        |  -3 table NUMBER_TABLE
        ----------------------------------
        */
            if(lua_isnumber(L,-2))
                cout<<"key:"<<lua_tonumber(L,-2)<<'\t';
            else if(lua_isstring(L,-2))
                cout<<"key:"<<lua_tostring(L,-2)<<'\t';
            if(lua_isnumber(L,-1))
                cout<<"value:"<<lua_tonumber(L,-1)<<endl;
            else if(lua_isstring(L,-1))
                cout<<"value:"<<lua_tostring(L,-1)<<endl;
    
        /*此时lua栈状态
        ----------------------------------
        |  -1 value
        |  -2 key
        |  -3 table NUMBER_TABLE
        ----------------------------------
        */
            lua_pop(L,1);
        /*此时lua栈状态
        ----------------------------------
        |  -1 key
        |  -2 table NUMBER_TABLE
        ----------------------------------
        */
        }
        lua_pop(L,1);
    
        /*此时lua栈状态
        ----------------------------------
        |  -1 table NUMBER_TABLE
        ----------------------------------
        */

    lua_next函数的工作流程现在大概了解了。还是婆婆妈妈的上一段文字吧:

    lua_next() 这个函数的工作过程是:
    1) 先从栈顶弹出一个 key
    2) 从栈指定位置的 table 里取下一对 key-value,先将 key 入栈再将 value 入栈
    3) 如果第 2 步成功则返回非 0 值,否则返回 0,并且不向栈中压入任何值

    第 2 步中从 table 里取出所谓“下一对 key-value”是相对于第 1 步中弹出的 key 的。table 里第一对 key-value 的前面没有数据,所以先用 lua_pushnil() 压入一个 nil 充当初始 key。

    注意开始的时候先用 lua_gettop() 取了一下 table 在栈中的正索引(前面说过了,在进行这个 lua_next() 过程之前先将 table 入栈,所以栈大小就是 table 的正索引),后面的 lua_next() 过程中不断的有元素出入栈,所以使用正索引来定位 table 比较方便。

    到了 table 中已经没有 key-value 对时,lua_next() 先弹出最后一个 key,然后发现已经没有数据了会返回 0,while 循环结束。所以这个 lua_next() 过程结束以后 table 就又位于栈顶了。


    展开全文
  • Python 3.2 迭代器的next函数

    千次阅读 2016-04-06 10:54:57
    在python中,使用iter函数可以获得有序聚合类型的迭代器,我个人将迭代器理解为带有next指针的单向链表,获取到的迭代器为...Python3.x以上的版本在使用next函数时需要注意的是:next()函数在3.x以上的版本更改为__next

    在python中,使用iter函数可以获得有序聚合类型的迭代器,我个人将迭代器理解为带有next指针的单向链表,获取到的迭代器为链表的表头,表头内容为空,next指针指向有序聚合类型的第一个元素。在访问链表最后一个元素的next指针时,python会报错StopIteration。

    Python3.x以上的版本在使用next函数时需要注意的是:next()函数在3.x以上的版本更改为__next__().


    使用for迭代器打印文件中的内容的代码如下:

    file_obj=open(r'E:\Project\Python\123.txt','r')
    
    for string in file_obj:
        string=string.rstrip('\n')
        print(string)
        
    file_obj.close()

    在上述代码中,文件对象file_obj为有序聚合类型,for循环会自动调用file_obj的迭代器,并调用该迭代器的next函数,知道发生 StopIteration错误。

    下边的代码模拟for循环中的迭代器,显式调用next函数访问字符串的元素。

    s='www.scu.edu.com'
    
    it=iter(s)
    length=len(s)
    i=0
    while i<length:
        print(it.__next__())
        i=i+1






    展开全文
  • NextDate函数小程序

    2007-06-21 16:26:48
    有关NextDate函数的小程序,可以做为测试练习
  • KMP算法中next函数的java实现

    千次阅读 2014-07-24 17:20:13
    KMP算法中next函数的java实现
  • 字符串next函数求值

    千次阅读 多人点赞 2017-10-11 21:31:26
    先看看next数据值的求解方法  位序 1 2 3 4 5 6 7 8 9 模式串 a b a a b c a b c  next值 0 1 1 2 2 3 1 2 3 next数组的求解方法是: 1.第一位的next值为0 2.第二位
  • KMP算法相比于朴素的模式匹配算法,其改进之处在于:利用已经得到的...该算法的关键在于next函数的计算,next函数的定义如下: 我们介绍两种方法来计算模式串的next函数 方法一:传统方法 方法二:简便方法...
  • next函数: 获取迭代器中的下一个值,会调用迭代器对象身上的next的方法 from collections import Iterable from collections import Iterator class MyList(object): def __init__(self):...
  • next_permutation函数

    千次阅读 2018-05-29 21:12:32
    next_permutation的函数声明:#include bool next_permutation( iterator start, iterator end); next_permutation函数的返回值是布尔类型,在STL中还有perv_permutation()函数 #include &lt;iostream&...
  • next_permutation函数用法举例

    万次阅读 多人点赞 2018-04-28 20:40:00
    按照STL文档的描述,next_permutation函数将按字母表顺序生成给定序列的下一个较大的排列,直到整个序列为降序为止。prev_permutation函数与之相反,是生成给定序列的上一个较小的排列。 这是一个求一个排序的下一...
  • 关于KMP算法中next函数的详细解析

    万次阅读 2017-05-15 20:46:24
    之前看到数据结构中字符串的模式匹配时,花了半天的时间,才把KMP算法中的next函数整明白了,结果过了几天在看到这时,只记得next[j+1]=next[j]+1,可是有时候能套公式正确算出,有时候就算不对,所以今天再重新理一...
  • 对express中next函数的一些理解

    千次阅读 2016-07-12 17:10:24
    转载自:http://cnodejs.org/topic/5757e80a8316c7cb1ad35bab对express中next函数的一些理解最近公司在使用node做前后端分离,采用的web框架是express,所以对express框架进行了深入的了解,前段时间写了篇关于...
  • NextDate函数白盒测试

    2010-05-30 10:41:25
    NextDate函数白盒测试 自己写的 软件测试白盒文档
  • 这里的主要目的是理解KMP算法中next[]数组的含义和实现过程:前缀函数主要是求出模式串中的next数组,那么什么是模式串呢?模式串模式串的概念很简单。举个例子:“给出一个字符串 T,再给出 n 个字符串 S1、S2...Sn...
  • KMP算法的next函数求解和分析过程

    千次阅读 2012-03-28 21:31:35
    假设KMP算法中的模式串为P,主串为S,那么该算法中的核心是计算出模式串的P的next函数。 KMP算法是在已知的模式串的next函数值的基础上进行匹配的。 由于本次只讨论next的求值过程,因此KMP算法的数学推理过程这里...
  • **3)** 如果Pj和P[next[k]]不相等了,为什么下次比较的是Pj和P[next[next[k]]]相比,为什么使用这样一个递推的过程来求解next[j+1]? 恕我愚钝,还请帮忙,给出针对以上问题的解释。 奖励如果不满意,可追加。谢谢!
  • QxmlStreamReader 中的readnext函数问题

    千次阅读 2011-09-28 19:30:19
    今天在看qt的xml解析的时候,发现一个有趣的现象,QxmlStreamReader 中的readnext函数每次读新值之前都会先读一个空值,不知Qt为何要做这样的设置。每次读完一个标签之后,直接读下一个不是很好吗?感觉真是奇怪,没...
  • 软件测试 - NextDate函数 - 测试用例详解:NextDate 函数包含三个变量:month(月份)、day(日期) 和 year(年),函数的输出为输入日期后一天的日期。 例如,输入为 2007年9月 9日,则函数的输出为 2007年9月10日 。
  • 软件测试NextDate函数测试用例详解
  • STL之next()函数和iota函数

    千次阅读 2015-11-16 10:17:41
    next函数:next(Iterator* it,int n) 返回值: 指向从it开始的第n个元素的迭代器。 示例: next(mylist.begin(),5) iota函数:STL序列依次递增函数 iota(Iterator* first,Iterator* last,T val) ...
  • 最近再刷笔试题的时候,发现了几道题需要求取字符串的next数组。 关于这部分知识,之前是有学过,代码也是比较简洁的,如下: public static int[] getNext(String ps) { char[] p = ps.toCharArray(); int[]...
  • 数据结构——关于KMP算法中next函数的详细解析

    万次阅读 多人点赞 2015-03-19 20:49:10
    之前看到数据结构中字符串的模式匹配时,花了半天的时间,才把KMP算法中的next函数整明白了,结果过了几天在看到这时,只记得next[j+1]=next[j]+1,可是有时候能套公式正确算出,有时候就算不对,所以今天再重新理一...
  • 至于KMP是什么next函数什么我就不多说了,直接上方法: 首先明确什么是前缀什么是后缀: abcd 前缀:abc ab a 后缀:d cd bcd 例1 abaabcac 这个字符串一共有8位,若没有前缀和后缀相等为其他情况,置1,...
  • KMP算法 next nextval函数

    千次阅读 2018-10-16 17:21:24
    #include&lt;malloc.h&...void get_next(SString T,int next[]) { int i=1,j=0,next[1]=0; while(i&lt;T.length) { if(j==0||T.ch[i]==T.ch[j]) { ++i; ++j; next[i]=j;...
  • next()函数返回迭代器的下一个项目,括号里面的元素必须是的可迭代的对象。 参考如下代码: lst=[1,2,30] for i in lst: print(i) next(lst) 运行结果: 1 2 30 ----------------------------------------------.....
  • 有人对next函数的递推算法只是处于会敲的状态但是却不理解,下面我来解释一下next函数递推算法的原理 在讲next函数递推算法的之前我们先回顾一下kmp算法的总体 int kmp(char *t char *p)//t是主传,p是匹配串 { i=1 ...
  • python next()函数

    万次阅读 2017-11-08 15:36:04
    最近在看python编程:从入门到实践里面读文件有用函数next(),对此函数不是很理解,看的代码如下:import csv filename='E:\python学习\pcc-master\chapter_16\sitka_weather_07-2014.csv' with open(filename) as f...
  • 数据结构KMP算法中next函数的求解思想及其解释

    千次阅读 多人点赞 2016-04-10 20:09:02
    这个只是简单的next数组的求法,并没有完全实现KMP算法,有待改进

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 758,429
精华内容 303,371
关键字:

next函数什么意思