精华内容
下载资源
问答
  • 对整个串求一遍next函数,从串结尾开始顺着next函数往前找<=len/3的最长串,假设串长为ans,由于next的性质,所以找到的串肯定满足E……E这种形式,然后就是在str[ans]-str[len-2*ans]中查找是不是包含E,找到就...

    设串为str, 串长为len。

    对整个串求一遍next函数,从串结尾开始顺着next函数往前找<=len/3的最长串,假设串长为ans,由于next的性质,所以找到的串肯定满足E……E这种形式,然后就是在str[ans]-str[len-2*ans]中查找是不是包含E,找到就输出,找不到就沿着next向下寻找,缩短串长。

    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    
    using namespace std;
    
    const int MAXN = 1000100;
    
    char str[MAXN];
    char tmp[MAXN];
    int nextval[MAXN];
    int len;
    
    void GetNextVal( char *s, int lenth )
    {
        int i = 0, j = -1;
        nextval[0] = -1;
        while ( i < lenth )
        {
            if ( j == -1 || s[i] == s[j] )
            {
                ++i, ++j;
                if ( s[i] != s[j] ) nextval[i] = j;
                else nextval[i] = nextval[j];
            }
            else j = nextval[j];
        }
        return;
    }
    
    bool KMP( char *t, char *s, int lenth, int lenn )
    {
        //GetNextVal( t, lenth );
        int i = 0, j = 0;
        while ( j < lenn )
        {
            if ( i == -1 || s[j] == t[i] )
            {
                ++i, ++j;
                if ( i == lenth ) return true;
            }
            else i = nextval[i];
            //if ( i == lenth ) return true;
        }
        return false;
    }
    
    int main()
    {
        int T;
        scanf( "%d", &T );
        while ( T-- )
        {
            scanf( "%s", str );
            len = strlen(str);
            GetNextVal( str, len );
            int ans = nextval[len];
            while ( ans > len/3 ) ans = nextval[ans];
            while ( ans > 0 )
            {
                if ( KMP( str, &str[ans], ans, len - ans - ans ) )
                    break;
                ans = nextval[ans];
            }
            if ( ans < 0 ) printf("%d\n", len/3);
            else printf( "%d\n", ans );
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/GBRgbr/p/3345186.html

    展开全文
  • public class KMPAlgorithm { public static void main(String[] args) { ... int[] array = kmpNext(str); for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } } /

    学习找部分匹配表也就是next函数的一点代码笔记:

    public class KMPAlgorithm {
        //测试
        public static void main(String[] args) {
            String str1 = "BBC ABCDAB ABCDABCDABDE";
            String str2 = "ABCDABD";
            int[] next = kmpNext(str2);
            System.out.println("next=" + Arrays.toString(next));
            int position = kmpSearch(str1, str2, next);
        }
    
        //写出我们的kmp搜索算法
    
        /**
         * @param str1 源字符串
         * @param str2 子串
         * @param next 部分匹配表, 是子串对应的部分匹配表
         * @return 如果是-1就是没有匹配到,否则返回第一个匹配的位置
         */
        public static int kmpSearch(String str1, String str2, int[] next) {
    
            //遍历
            for (int i = 0, j = 0; i < str1.length(); i++) {
                
                //需要处理 str1.charAt(i) != str2.charAt(j), 去调整j的大小
                //KMP算法核心点, 可以验证...
                while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                    j = next[j - 1];
                }
    
                if (str1.charAt(i) == str2.charAt(j)) {
                    j++;
                }
                if (j == str2.length()) {//找到了 // j = 3 i
                    return i - j + 1;
                }
            }
            return -1;
        }
    
        //获取到一个字符串(子串) 的部分匹配值表
        public static int[] kmpNext(String dest) {
            //创建一个next 数组保存部分匹配值
            int[] next = new int[dest.length()];
            next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
            for (int i = 1, j = 0; i < dest.length(); i++) {
                //首先明确 i指向尾巴 一直往后走 而j 看相等的情况 有不相等的j就往回走
                //如果遇到连续相等 那么j连续相加表示匹配
                //当dest.charAt(i) != dest.charAt(j) ,我们需要从next[j-1]获取新的j
                //直到我们发现 有  dest.charAt(i) == dest.charAt(j)成立才退出
                //这是kmp算法的核心点
                //如果此时i和j处的字符不同 那么 就把j更新一下 回退!!
                //next[j-1]给到j 使得j 回退 这个公式是用数学推导的 比较麻烦
                int nonSense;
                while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                    j = next[j - 1];//j遇到不相同的字符时 回退
                }
    
                //当dest.charAt(i) == dest.charAt(j) 满足时,部分匹配值就是+1
                if (dest.charAt(i) == dest.charAt(j)) {
                    j++;
                }
                //此时要么j为0 正好给到next[i] 说明i处为止 前缀和后缀没有公共部分 此时i处部分匹配值为0
                //在之前j的基础上 每找到一个dest.charAt(i) == dest.charAt(j)时 j++
                //此时把j给到next[i] 实现更新next[i] 作为i处的部分匹配值
                next[i] = j;
            }
            return next;
        }
    }
    
    
    
    展开全文
  • ----------------------- ...由上,next【i】=j,两段红色的字符串相等(两个字符串完全相等),s[k....j]==s[m....i] 设s[x...j]=s[j....i](xj=ji) 则可得,以下简写字符串表达方式 kj=kx+xj; mi=m

    -----------------------

    -----------------------

     k    m        x      j       i

    由上,next【i】=j,两段红色的字符串相等(两个字符串完全相等),s[k....j]==s[m....i]

    设s[x...j]=s[j....i](xj=ji)

    则可得,以下简写字符串表达方式

    kj=kx+xj;

    mi=mj+ji;

    因为xj=ji,所以kx=mj,如下图所示

     

    -------------

          -------------

     k   m        x     j   

    看到了没,此时又重复上面的模型了,kx=mj,所以可以一直这样递推下去

    所以可以推出一个重要的性质len-next[i]为此字符串的最小循环节(i为字符串的结尾),另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i]);


    展开全文
  • 转自大牛的博客:http://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html ----------------------- ----------------------- ...由上,next【i】=j,两段红色的字符串相等(两个

    转自大牛的博客:http://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html



    -----------------------

    -----------------------

     k    m        x      j       i

    由上,next【i】=j,两段红色的字符串相等(两个字符串完全相等),s[k....j]==s[m....i]

    设s[x...j]=s[j....i](xj=ji)

    则可得,以下简写字符串表达方式

    kj=kx+xj;

    mi=mj+ji;

    因为xj=ji,所以kx=mj,如下图所示

     

    -------------

          -------------

     k   m        x     j   

    看到了没,此时又重复上面的模型了,kx=mj,所以可以一直这样递推下去

    所以可以推出一个重要的性质len-next[i]为此字符串的最小循环节(i为字符串的结尾),另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i]);

     

    展开全文
  • 其实就是对于next函数的使用,先把两个字符串合成一个,然后因为是公共部分,所以next【len】也应该小于第一个和第二个字符串最小长度。 #include #include #include using namespace std; char st[1000005],sa...
  • 模拟KMP失配函数next过程分析
  • KMPnext函数

    2014-02-19 09:04:45
    今天花了半天的时间,终于把KMP算法中的next函数整明白了 先看看next数据值的求解方法 位序 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2 next数
  • 首先学过kmp的都知道要写两个函数,一个计算next数组,一个kmp主体函数,那么next数组里存的到底是啥呢。首先答案是:next[i]存的是字符串[0,i]的前后缀最长公共长度。下面先解释下前后缀。 引用张别人的图: 也...
  • kmp算法next函数

    2019-02-26 03:28:36
    转载于:https://juejin.im/post/5c74b20751882554cc6c5508
  • KMP算法 next函数 代码解析

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

    2015-11-11 11:26:49
     next函数是指当前待匹配的字符失配的时候,当前字符之前的字符串的最大相同前后缀的长度。(匹配当前字符,求得next函数对应的是下一个字符的next值。何解?使用next函数都是在比对当前字符失败的情况下,调用当前...
  • 先看看next数据值的求解方法 位序 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2 next数组的求解方法是: 1.第一位的next值为0 2.第二位的next
  • KMP算法的next函数详解

    千次阅读 2017-03-09 20:45:43
    KMP算法的next函数详解
  • 经典算法之KMPnext函数解析

    千次阅读 2013-10-28 13:51:31
    KMP字符串模式匹配最难理解的地方在于next函数的的算法,本人结合《数据结构》严蔚敏版,给出了一个更为详细和容易理解的解析。 kmp算法链接:http://blog.csdn.net/v_JULY_v/article/details/6545192
  • KMP算法相比于朴素的模式匹配算法,其改进之处在于:利用已经得到的...该算法的关键在于next函数的计算,next函数的定义如下: 我们介绍两种方法来计算模式串的next函数 方法一:传统方法 方法二:简便方法...
  • ![这算法我看不大懂,要怎么进入循环呢 next[-1]有值吗[图片说明](https://img-ask.csdn.net/upload/201704/04/1491310302_979080.png)
  • 修改KMPNext函数

    2009-08-23 13:01:00
    KMP的核心就是他的Next函数, 看代码都要晕几次才能理解,要证明为什么这样子真的是头都大,不过我看过几个后觉得还可以改的更容易理解,就是当前字符先跟自己下标的字符比较,如果相等就是说下个字符的右偏移就是...
  • 这里的主要目的是理解KMP算法中next[]数组的含义和实现过程:前缀函数主要是求出模式串中的next数组,那么什么是模式串呢?模式串模式串的概念很简单。举个例子:“给出一个字符串 T,再给出 n 个字符串 S1、S2...Sn...
  • KMP算法中next函数的java实现

    千次阅读 2014-07-24 17:20:13
    KMP算法中next函数的java实现
  • 前言: 前段时间学习和字符串相关的算法,自然学到了KMP算法(解决单字符串匹配...引入: KMP算法其实就是两个部分,①:前缀函数(求前缀数组)②:匹配部分。 那么什么是前缀函数呢??这是本篇文章的内容,...
  • KMP算法之next函数

    2020-04-17 03:11:36
    #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<cstring> using namespace std;...int next[maxn]; void getnext(char s[],...
  • KMP算法-next函数求解

    2016-08-03 16:50:00
    KMP函数求解:一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为KMP算法。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体...
  • 至于KMP是什么,next函数是什么我就不多说了,直接上方法: 首先明确什么是前缀什么是后缀: abcd 前缀:abc ab a 后缀:d cd bcd 例1 abaabcac 这个字符串一共有8位,若没有前缀和后缀相等为其他情况,置1,...
  • KMP算法 - 求NEXT函数

    2016-11-21 11:53:57
    在数据结构与算法这门课中,我们接触到了KMP算法,一般使用KMP算法之前我们要求解一个NEXT函数值。  求解过程挺简单,我在这里... 串 ‘ababaaababaa’ 的NEXT函数数组为________。    i 值 1  2  3  4  5
  • KMP算法-next函数介绍

    2021-08-11 16:25:15
    KMP算法中最核心的部分之一便是next函数,关于next函数,它是为了在遍历字符串子串时可以选择性跳过一些重复判断的字符,极大的减小了算法的时间复杂度。形成一个next数组,数组中存放跳过的数字。 例: a a b a a ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,394
精华内容 4,157
关键字:

kmpnext函数