kmp 数据结构_数据结构 kmp - CSDN
  • 数据结构KMP算法

    2018-10-18 17:39:06
    一. 首先求next值 例如: 模式串 a b a a b c a c  next值 0 1 1 2 2 3 1 2 next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。...

    一. 首先求next值

    例如: 模式串 a b a a b c a c          

                 next值 0 1 1 2 2 3 1 2

    next数组的求解方法是:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,向前继续寻找next值对应的内容来与前一位进行比较,直到找到某个位上内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为1。

    1.前两位必定为0和1。

    2.计算第三位的时候,看第二位b的next值,为1,则把b和1对应的a进行比较,不同,则第三位a的next的值为1,因为一直比到最前一位,都没有发生比较相同的现象。

    3.计算第四位的时候,看第三位a的next值,为1,则把a和1对应的a进行比较,相同,则第四位a的next的值为第三位a的next值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。

    4.计算第五位的时候,看第四位a的next值,为2,则把a和2对应的b进行比较,不同,则再将b对应的next值1对应的a与第四位的a进行比较,相同,则第五位的next值为第二位b的next值加上1,为2。因为是在第二位实现了其next值对应的值与第四位的值相同。

    5.计算第六位的时候,看第五位b的next值,为2,则把b和2对应的b进行比较,相同,则第六位c的next值为第五位b的next值加上1,为3,因为是在第五位实现了其next值对应的值与第五位相同。

    6.计算第七位的时候,看第六位c的next值,为3,则把c和3对应的a进行比较,不同,则再把第3位a的next值1对应的a与第六位c比较,仍然不同,则第七位的next值为1。 7.计算第八位的时候,看第七位a的next值,为1,则把a和1对应的a进行比较,相同,则第八位c的next值为第七位a的next值加上1,为2,因为是在第七位和实现了其next值对应的值与第七位相同。

    二. nextval值的求法

    例如主串为“aaabaaaab”、  

            模式串为“aaaab”

    在计算nextval之前要先弄明白,nextval是为了弥补next函数在某些情况下的缺陷而产生的。 例如主串为“aaabaaaab”、模式串为“aaaab”那么,比较的时候就会发生一些浪费的情况:比较到主串以及模式串的第四位时,发现其值并不相等,据我们观察,我们可以直接从主串的第五位开始与模式串进行比较,而事实上,却进行了几次多余的比较。使用nextval可以去除那些不必要的比较次数。

    模式串       a b a a b c a c

    next值       0 1 1 2 2 3 1 2

    nextval值  0 1 0 2 1 3 0 2

    1.第一位的nextval值必定为0,第二位如果于第一位相同则为0,如果不同则为1。  

    2.第三位的next值为1,那么将第三位和第一位进行比较,均为a,相同,则,第三位的nextval值为0。

    3.第四位的next值为2,那么将第四位和第二位进行比较,不同,则第四位的nextval值为其next值,为2。

    4.第五位的next值为2,那么将第五位和第二位进行比较,相同,第二位的next值为1,则继续将第二位与第一位进行比较,不同,则第五位的nextval值为第二位的next值,为1。

    5.第六位的next值为3,那么将第六位和第三位进行比较,不同,则第六位的nextval值为其next值,为3。

    6.第七位的next值为1,那么将第七位和第一位进行比较,相同,则第七位的nextval值为0。

    7.第八位的next值为2,那么将第八位和第二位进行比较,不同,则第八位的nextval值为其next值,为2。

    三. KMP算法

    • KMP算法是用来处理字符串匹配的。换句话说,给你两个字符串,你需要回答,B串是否是A串的子串(A串是否包含B串)。例如”Today is Tuesday”.中是否包含”day”,在哪些位置包含。
    • 这个算法是由Knuth、Morris、Pratt三个提出来的,取了这三个人的名字的头一个字母。
    • 假如,A="abababaababacb",B="ababacb",我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示,A[i-j+ 1..i]与B[1..j]完全相等。 也就是说,i是不断增加的,随着i的增加j相应地变化,且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符(j当然越大越好),现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时,i和j各加一;什么时候j=m了,我们就说B是A的子串(B串已经整完了),并且可以根据这时的i值算出匹配的位置。
    • 当A[i+1]<>B[j+1],KMP的策略是调整j的位置(减小j值)使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配(从而使得i和j能继续增加)。我们看一看当 i=j=5时的情况。位置。

              i: 1 2 3 4 5 6 7 8 9 10

             A: a b a b a b a a b a b …

              B: a b a b a c b

               j: 1 2 3 4 5 6 7 8 9 10

    • 从上面的这个例子,我们可以看到,新的j可以取多少与i无关,只与B串有关。我们完全可以预处理出这样一个数组P[j],表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时,新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
    • 事实上,有可能j到了0仍然不能满足A[i+1]=B[j+1](比如A[8]="d"时)。因此,准确的说法是,当j=0了时,我们增加i值但忽略j直到出现A[i]=B[1]为止。

    算法实现:

    最后的j:=P[j]是 为了让程序继续做 下去,因为我们有 可能找到多处匹配。 这个程序或许 比想像中的要简单, 因为对于i值的不断 增加,代码用的是for循环。因此,这个代码可以这样形象地理解:扫描字符串A,并更新可以匹配到B的什么位置。

     

     

     

     

    展开全文
  • 申明:此篇博文为转载博文,原博文地址:https://www.cnblogs.com/yjiyjige/p/3263858.html什么是KMP算法:KMP是三位大牛:D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。其中第一位就是《计算机程序设计艺术》的...

    申明:此篇博文为转载博文,原博文地址:https://www.cnblogs.com/yjiyjige/p/3263858.html

    什么是KMP算法:

    KMP是三位大牛:D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。其中第一位就是《计算机程序设计艺术》的作者!!

    KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体位置,否则返回-1(常用手段)。

     

    首先,对于这个问题有一个很单纯的想法:从左到右一个个匹配,如果这个过程中有某个字符不匹配,就跳回去,将模式串向右移动一位。这有什么难的?

    我们可以这样初始化:

     

    之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动,如果不一致,如下图:

     

     

    A和E不相等,那就把i指针移回第1位(假设下标从0开始),j移动到模式串的第0位,然后又重新开始这个步骤:

     

    基于这个想法我们可以得到以下的程序:

    复制代码
     1 /**
     2 
     3  * 暴力破解法
     4 
     5  * @param ts 主串
     6 
     7  * @param ps 模式串
     8 
     9  * @return 如果找到,返回在主串中第一个字符出现的下标,否则为-1
    10 
    11  */
    12 
    13 public static int bf(String ts, String ps) {
    14 
    15     char[] t = ts.toCharArray();
    16 
    17     char[] p = ps.toCharArray();
    18 
    19     int i = 0; // 主串的位置
    20 
    21     int j = 0; // 模式串的位置
    22 
    23     while (i < t.length && j < p.length) {
    24 
    25        if (t[i] == p[j]) { // 当两个字符相同,就比较下一个
    26 
    27            i++;
    28 
    29            j++;
    30 
    31        } else {
    32 
    33            i = i - j + 1; // 一旦不匹配,i后退
    34 
    35            j = 0; // j归0
    36 
    37        }
    38 
    39     }
    40 
    41     if (j == p.length) {
    42 
    43        return i - j;
    44 
    45     } else {
    46 
    47        return -1;
    48 
    49     }
    50 
    51 }
    复制代码

    上面的程序是没有问题的,但不够好!(想起我高中时候数字老师的一句话:我不能说你错,只能说你不对~~~)

    如果是人为来寻找的话,肯定不会再把i移动回第1位,因为主串匹配失败的位置前面除了第一个A之外再也没有A了,我们为什么能知道主串前面只有一个A?因为我们已经知道前面三个字符都是匹配的!(这很重要)。移动过去肯定也是不匹配的!有一个想法,i可以不动,我们只需要移动j即可,如下图:

     

    上面的这种情况还是比较理想的情况,我们最多也就多比较了再次。但假如是在主串“SSSSSSSSSSSSSA”中查找“SSSSB”,比较到最后一个才知道不匹配,然后i回溯,这个的效率是显然是最低的。

     

    大牛们是无法忍受“暴力破解”这种低效的手段的,于是他们三个研究出了KMP算法。其思想就如同我们上边所看到的一样:“利用已经部分匹配这个有效信息,保持i指针不回溯,通过修改j指针,让模式串尽量地移动到有效的位置。”

     

    所以,整个KMP的重点就在于当某一个字符与主串不匹配时,我们应该知道j指针要移动到哪

     

    接下来我们自己来发现j的移动规律:

     

    如图:C和D不匹配了,我们要把j移动到哪?显然是第1位。为什么?因为前面有一个A相同啊:

     

    如下图也是一样的情况:

     

    可以把j指针移动到第2位,因为前面有两个字母是一样的:

     

    至此我们可以大概看出一点端倪,当匹配失败时,j要移动的下一个位置k。存在着这样的性质:最前面的k个字符和j之前的最后k个字符是一样的

    如果用数学公式来表示是这样的

    P[0 ~ k-1] == P[j-k ~ j-1]

    这个相当重要,如果觉得不好记的话,可以通过下图来理解:

     

    弄明白了这个就应该可能明白为什么可以直接将j移动到k位置了。

    因为:

    当T[i] != P[j]时

    有T[i-j ~ i-1] == P[0 ~ j-1]

    由P[0 ~ k-1] == P[j-k ~ j-1]

    必然:T[i-k ~ i-1] == P[0 ~ k-1]

    公式很无聊,能看明白就行了,不需要记住。

    这一段只是为了证明我们为什么可以直接将j移动到k而无须再比较前面的k个字符。

     

    好,接下来就是重点了,怎么求这个(这些)k呢?因为在P的每一个位置都可能发生不匹配,也就是说我们要计算每一个位置j对应的k,所以用一个数组next来保存,next[j] = k,表示当T[i] != P[j]时,j指针的下一个位置。

     

    很多教材或博文在这个地方都是讲得比较含糊或是根本就一笔带过,甚至就是贴一段代码上来,为什么是这样求?怎么可以这样求?根本就没有说清楚。而这里恰恰是整个算法最关键的地方。

    复制代码
     1 public static int[] getNext(String ps) {
     2 
     3     char[] p = ps.toCharArray();
     4 
     5     int[] next = new int[p.length];
     6 
     7     next[0] = -1;
     8 
     9     int j = 0;
    10 
    11     int k = -1;
    12 
    13     while (j < p.length - 1) {
    14 
    15        if (k == -1 || p[j] == p[k]) {
    16 
    17            next[++j] = ++k;
    18 
    19        } else {
    20 
    21            k = next[k];
    22 
    23        }
    24 
    25     }
    26 
    27     return next;
    28 
    29 }
    复制代码

    这个版本的求next数组的算法应该是流传最广泛的,代码是很简洁。可是真的很让人摸不到头脑,它这样计算的依据到底是什么?

    好,先把这个放一边,我们自己来推导思路,现在要始终记住一点,next[j]的值(也就是k)表示,当P[j] != T[i]时,j指针的下一步移动位置

    先来看第一个:当j为0时,如果这时候不匹配,怎么办?

     

    像上图这种情况,j已经在最左边了,不可能再移动了,这时候要应该是i指针后移。所以在代码中才会有next[0] = -1;这个初始化。

    如果是当j为1的时候呢?

     

    显然,j指针一定是后移到0位置的。因为它前面也就只有这一个位置了~~~

     

    下面这个是最重要的,请看如下图:

      

     

    请仔细对比这两个图。

    我们发现一个规律:

    当P[k] == P[j]时,

    有next[j+1] == next[j] + 1

    其实这个是可以证明的:

    因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。(next[j] == k)

    这时候现有P[k] == P[j],我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。

    即:P[0 ~ k] == P[j-k ~ j],即next[j+1] == k + 1 == next[j] + 1。

    这里的公式不是很好懂,还是看图会容易理解些。

     

    那如果P[k] != P[j]呢?比如下图所示:

     

    像这种情况,如果你从代码上看应该是这一句:k = next[k];为什么是这样子?你看下面应该就明白了。

     

    现在你应该知道为什么要k = next[k]了吧!像上边的例子,我们已经不可能找到[ A,B,A,B ]这个最长的后缀串了,但我们还是可能找到[ A,B ]、[ B ]这样的前缀串的。所以这个过程像不像在定位[ A,B,A,C ]这个串,当C和主串不一样了(也就是k位置不一样了),那当然是把指针移动到next[k]啦。

     

    有了next数组之后就一切好办了,我们可以动手写KMP算法了:

    复制代码
     1 public static int KMP(String ts, String ps) {
     2 
     3     char[] t = ts.toCharArray();
     4 
     5     char[] p = ps.toCharArray();
     6 
     7     int i = 0; // 主串的位置
     8 
     9     int j = 0; // 模式串的位置
    10 
    11     int[] next = getNext(ps);
    12 
    13     while (i < t.length && j < p.length) {
    14 
    15        if (j == -1 || t[i] == p[j]) { // 当j为-1时,要移动的是i,当然j也要归0
    16 
    17            i++;
    18 
    19            j++;
    20 
    21        } else {
    22 
    23            // i不需要回溯了
    24 
    25            // i = i - j + 1;
    26 
    27            j = next[j]; // j回到指定位置
    28 
    29        }
    30 
    31     }
    32 
    33     if (j == p.length) {
    34 
    35        return i - j;
    36 
    37     } else {
    38 
    39        return -1;
    40 
    41     }
    42 
    43 }
    复制代码

    和暴力破解相比,就改动了4个地方。其中最主要的一点就是,i不需要回溯了。

     

    最后,来看一下上边的算法存在的缺陷。来看第一个例子:

     

    显然,当我们上边的算法得到的next数组应该是[ -1,0,0,1 ]

    所以下一步我们应该是把j移动到第1个元素咯:

     

    不难发现,这一步是完全没有意义的。因为后面的B已经不匹配了,那前面的B也一定是不匹配的,同样的情况其实还发生在第2个元素A上。

    显然,发生问题的原因在于P[j] == P[next[j]]

    所以我们也只需要添加一个判断条件即可:

    复制代码
    public static int[] getNext(String ps) {
    
        char[] p = ps.toCharArray();
    
        int[] next = new int[p.length];
    
        next[0] = -1;
    
        int j = 0;
    
        int k = -1;
    
        while (j < p.length - 1) {
    
           if (k == -1 || p[j] == p[k]) {
    
               if (p[++j] == p[++k]) { // 当两个字符相等时要跳过
    
                  next[j] = next[k];
    
               } else {
    
                  next[j] = k;
    
               }
    
           } else {
    
               k = next[k];
    
           }
    
        }
    
        return next;
    
    } 
    复制代码

    好了,至此。KMP算法也结束了。

    很奇怪,好像不是很难的东西怎么就把我困住这么久呢?

    仔细想想还是因为自己太浮躁了,以前总是草草应付,很多细节都没弄清楚,就以为自己懂了。结果就只能是似懂非懂的。要学东西真的需要静下心来。

    展开全文
  • 本文将从7个方面对KMP算法以个人理解进行描述,参考书目:严蔚敏教授的《数据结构(C语言版)》 目录 KMP算法 1.什么是KMP算法? 2.经典字符串匹配算法。(老法子,效率低) 3.如何实现next数组? 4.Next...

    KMP算法

            本文将从7个方面对KMP算法以个人理解进行描述,参考书目:严蔚敏教授的《数据结构(C语言版)》

     

    目录

    KMP算法

    1.什么是KMP算法?

    2.经典字符串匹配算法。(老法子,效率低)

    3.如何实现next数组?

    4.Next数组是完美的标记数组吗?

    5.KMP算法过程讲解

    6.实现算法

    7.对与经典算法比较


    1.什么是KMP算法?

            KMP算法是为了解决字符串匹配效率问题的优化算法。(非定义)

    2.经典字符串匹配算法。(老法子,效率低)

            给出两个字符串S母串、T子串以及正整数pos,要求从S母串中第pos位置开始进行匹配直到找到一个与T子串相同的字符串为止,并返回该字符串开始的位置。(注:在本算法中所有的下标均从0开始。 #重新定义数据结构SString,课本上用的是SString,字符串下标从1开始,0下标表示的是字符串的长度。此处直接使用已有数据类型string,并用s.length()表示字符串长度)

    算法实现如下:

    #include<iostream>
    
    #include<string>
    
    using namespace std;
    
    
    
    int init(string S, string T, int pos){
    
    if (S.length() < T.length() || pos > S.length())
    
              return 0;
    
    int i = pos - 1 , j = 0 ;
    
    while(i < S.length() && j < T.length() ){
    
              cout<<S[i]<<"\t"<<T[j]<<endl;
    
              cout<<i<<"\t"<<j<<endl;
    
              if(S[i]==T[j]){
    
                      i++;
    
                      j++;
    
              }else{
    
                      i = i-j+1 ;
    
                      j = 0 ;
    
              }              
    
    }
    
    if (j==T.length())
    
              return i - j + 1;
    
    return 0;
    
    }
    
    
    
    int main(){
    
    //主函数pos按照字符串的位置进行输入,pos >= 1
    
    string S,T;
    
    int pos = 1;
    
    //S= "ababcabcacbab"   T="abcac"
    
    cin>>S>>T>>pos;
    
    cout<<S<<endl<<T<<endl;
    
    cout<<init(S,T,pos)<<endl;
    
    return 0;
    
    }

            此种算法的原理是:各位一一比较,相同则比较下一位,不同则进行回退,子串重新从第1位开始,母串则后推一位。此种算法最快需要比较n次(子串的长度),最慢则需比较m*n次,举例说明(1、“asdasdadad”和“asd”   2、字符串“00000000001”和字符串“0001”)

            由例2我们不难看出,我们第一次比较完后发现s串的第4位及以前均为0,而T串的前三位也为0,所以第二次比较的时候,无需将子串的第1位和母串的第2位进行比较,则只需从子串的第3位和母串的第4位进行比较即可,即只需子串指针进行回溯,但如何实现这个功能呢?或者说,如何省去中间的比较过程呢?在此我们希望有一个数组可以记录,出现不匹配时对字串进行回溯的位置。这是我们引入一个数组next。

    3.如何实现next数组?

            这一问题属于KMP算法中的一大难点,它有两种计算方法,一种是针对考试过程中笔算,第二种则是针对机试中的编程问题。

            第一种计算方法,这种方法是从网上的一个视频中学到的,用起来是莫名的舒爽。

            (原视频找了好久没找到,来自哔哩哔哩的一段5~6分钟的英文讲解视频)用下面的方法也一样,用熟了自然就快了。

            第二种方法则是根据原理一步一步理解实现的。

                    1.先写出子串T,“abcdabcacd”;

                    2.对其进行标记下标,与参考资料不同,在此字符串是以0为下表开始的,如下表:

    下标

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    字符

    a

    b

    c

    d

    A

    b

    c

    a

    c

    d

    Next

     

     

     

     

     

     

     

     

     

     

    现在的任务即是将表格的第三行进行填充,我们本着的原则就是,能少往前翻就少往前翻。

    第一个字符“a”,若是第一个字符就不相同,那么后面的肯定不考虑,所以讲母串向后移一位(在此所有母串的操作暂且不用理会),下一次还是从第一位开始比,所以此处填0,但考虑到和母串一起变化且方便操作,此处改为-1;

    第二个字符若不同,则比较前面的字符串,前面的字符串为“a”,没有前后缀之说,所以此处也应填0;

    第三个字符若不同,前面的字符串为“ab”,前后缀不同,所以此处返回0;

    第四个字符同理,第五个字符若不同,比较字符串“abcd”,所以此处为0;

    第六个字符若不同,比较字符串“abcda”,前后子串“a”相同,则下一次比较无需比较第一位,直接从第二个字符开始比较,即返回1;

    第七个字符若不同,比较字符串“abcdab”,前后子串“ab”相同,则下次比较可直接从第三个字符开始比较,即返回2;

    第八九十个字符位同理。-1 0 0 0 0 1 2 3 1 0

                用图和公式表示就是,

                     算法实现见后文。(字丑勿笑,“前后缀”一名词不知合适否。)

    4.Next数组是完美的标记数组吗?

            答案显然不是。若如例3所提:字符串“00010001001010000001”和字符串“0000001”进行比较。

            (从1开始记位)当i=4,j=4时,我们不难发现出现了不匹配的情况,若按照上问题到的next数组进行比较的话,则还需要进行 (i,j) = (4,3)、(4,2)、(4,1)的比较,而从字符串上我们能够很清楚的看到j=1、2、3、4时,子串上的字符是完全一样的,所以这些比较就没有必要进行,应该直接从(i,j) = (5,1)进行比较,即让子串中的指针进行了next[next[…..]]的跳跃,如何能够实现这个效果呢?这里引入一个新的数组名称为nextval。

            这个数组的获得与上个数组的获得有何不同呢?他们之间的差别其实非常小,仅需在其中加一个判断语句,判断T[j]和T[k]是否相等,如果相等则当前nextval的值与k位上的nextval值相等,否则则和next数组获取值的方式相同。

    5.KMP算法过程讲解

            KMP算法和的执行过程与普通的字符串查找算法大体无异,而仅有的差别就是,当遇到子母串字符不相匹配时,原算法是子母串指针均进行回溯,而KMP算法则是,子串指针根据next数组进行回溯,母串指针位置不变。即理解KMP算法的前提得将经典的算法过程进行熟悉掌握。

    6.实现算法

    /*编译环境:
    
    win10专业版
    
    DEV C++ 5.11
    
    TDM-GCC 4.9.2 64bit
    
    
    
    */
    
    #include<iostream>
    
    #include<string>
    
    using namespace std;
    
    
    
    int init(string S, string T, int pos);
    
    int get_Next(string T,int next[]);
    
    int get_Nextval(string T,int nextval[]);
    
    int KMP(string S, string T, int pos);
    
    
    
    int main(){
    
            //主函数pos按照字符串的位置进行输入,pos >= 1
    
            string S,T;
    
            int pos = 1;
    
            //S= "ababcabcacbab"   T="abcac"
    
            cin>>S>>T>>pos;
    
            cout<<S<<endl<<T<<endl;
    
            cout<<KMP(S,T,pos)<<endl;
    
            return 0;
    
    }
    
    
    
    int init(string S, string T, int pos){
    
            if (S.length() < T.length() || pos > S.length())
    
                     return 0;
    
            int i = pos - 1 , j = 0 ;
    
            while(i < S.length() && j < T.length() ){
    
                     cout<<S[i]<<"\t"<<T[j]<<endl;
    
                     cout<<i<<"\t"<<j<<endl;
    
                     if(S[i]==T[j]){
    
                             i++;
    
                             j++;
    
                     }else{
    
                             i = i-j+1 ;
    
                             j = 0 ;
    
                     }              
    
            }
    
            if (j==T.length())
    
                     return i - j + 1;
    
            return 0;
    
    }
    
    
    
    int get_Next(string T,int next[]){
    
            next[0] = -1;
    
            int k = -1 , j = 0;//j一直增加,不进行回溯
    
            while(j < T.length()-1){
    
                     if(k==-1||T[k] == T[j]){
    
                             k++;
    
                             j++;
    
                             next[j] = k;
    
                             //cout << "next"<<j<<"\t"<<k<<endl;
    
                     } else
    
                             k = next[k];
    
            }
    
    }
    
    
    
    int KMP(string S, string T, int pos){
    
            if(S.length()<T.length() ||pos>S.length())
    
                     return 0 ;
    
            int next[T.length()];
    
            //get_Next(T,next);//求next
    
            get_Nextval(T,next); //求nextval
    
            int i = pos-1,j= 0;
    
            while(i<S.length() && j<int(T.length())){
    
                     //cout<<i<<"\t"<<j<<endl;
    
                     //cout<<S[i]<<"\t"<<T[j]<<endl;
    
                     if ( j == -1 ||S[i]==T[j]){
    
                             i++;
    
                             j++;
    
                     }else{
    
                             j = next[j];
    
                     }
    
                     //cout<<j<<endl;
    
            }
    
            if (j==T.length())
    
                     return i-j+1;
    
            return 0;
    
    }
    
    
    
    int get_Nextval(string T,int nextval[]){
    
            nextval[0] = -1;
    
            int k = -1 , j = 0;//j一直增加,不进行回溯
    
            while(j < T.length()-1){
    
                     if(k==-1||T[k] == T[j]){
    
                             k++;
    
                             j++;
    
                             if(T[k] == T[j])
    
                                      nextval[j] = nextval[k]; //可以套nextval的循环
    
                             else nextval[j] = k; //取k值
    
                             //cout << "next"<<j<<"\t"<<k<<endl;
    
                     } else
    
                             k = nextval[k];
    
            }
    
    }
    
    
    
    
    
    /*
    
    ababcabcacbab
    
    abcac
    
    1
    
    
    */
    
    

    7.对与经典算法比较

          因为子串的长度远比母串小,所以对子串求next数组消耗的时间来换取来回重复回溯母串字符指针的时间这一操作来讲,我们认为是很划算的,因此说KMP算法的效率比较高。但是一般情况下,经典算法的耗时基本趋向o(n+m),所以到现在为止经典算法还没有被完全替代,但对于文件扫描等大型的比较操作来讲,KMP算法的优势就会很明显。

    修改记录:

    2019-7-7:

            KMP函数中while循环中的判断条件添加了强制转换。因为 字符串的 .length()方法返回的是 unsigned long long (int)类型和int型数据比较一直出错 (课本上算法中,第一个字符下标从1开始,不会出现这种比较出错得情况 )

     

    展开全文
  • 数据结构实验之串一:KMP简单应用 Time Limit: 1000MS Memory limit: 65536K 题目描述 给定两个字符串string1和string2,判断string2是否为string1的子串。 输入  输入包含多组数据,每组...

    数据结构实验之串一:KMP简单应用

    Time Limit: 1000MS Memory limit: 65536K

    题目描述

    给定两个字符串string1和string2,判断string2是否为string1的子串。

    输入

     输入包含多组数据,每组测试数据包含两行,第一行代表string1(长度小于1000000),第二行代表string2(长度小于1000000),string1和string2中保证不出现空格。

    输出

     对于每组输入数据,若string2是string1的子串,则输出string2在string1中的位置,若不是,输出-1。

    示例输入

    abc
    a
    123456
    45
    abc
    ddd
    

    示例输出

    1
    4
    -1

    ///ACcode

    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    const int maxn=10000010;
    typedef struct
    {
        char *top,*base;
        int Size;
        int len;
    } String;
    
    void Creat(String &s)  ///建串
    {
        s.base=new char[maxn];
        s.top=s.base;
        s.Size=maxn;
        s.len=0;
    }
    
    void push(String &s,char c) ///入串...函数名有点眼熟...
    {
        s.top++;
        *s.top=c;
        s.len++;
    }
    
    void add(String &s,char st[]) ///为了使 两个串 下标从零开始
    {
        int i;
        for (i=0; st[i]; i++)
        {
            push(s,st[i]);
        }
    }
    
    void getnext(String &s,int next[]) /// 相当于KMP函数 其实就是和本身比较来寻找next[]数组;建议先看下面的KMP函数
    {
        int i=1,j=0; ///j从 1 开始的话 next[2]=2;显然不符合next[]数组....
        next[1]=0;
        while(i<=s.len)
        {
            if (j==0||s.base[i] == s.base[j])
            {
                i++;
                j++;
                next[i]=j; /// 动态演示中很明显看出 前 j 个字符已经匹配
            }
    
            else
            {
                j=next[j]; /// 失配时 j“跳”到next[j]位置(也就是说next[j]之前的位置已经匹配)
            }
        }
    }
    
    void kmp(String &st,String &pt,int next[])  ///kmp ,st主串 pt模式串
    {
        int i=1,j=1;
        while(i<=st.len && j<=pt.len)
        {
            if(j==0||st.base[i] == pt.base[j])
            {
                i++;
                j++;
            }
            else
            {
                j=next[j]; /// 失配时 j“跳”到next[j]位置(也就是说next[j]之前的位置已经匹配)
            }
        }
        if (j>pt.len) ///说明模式串pt匹配完成
        {
            cout<<i-pt.len<<endl;
        }
        else  ///串st遍历先完了,则pt不是st子串
        {
            cout<<"-1"<<endl;
        }
    }
    
    void  print(String &s) ///打印
    {
        int i;
        for (i=1; i<=s.len; i++)
        {
            cout<<s.base[i];
        }
        cout<<endl;
    }
    
    int main()
    {
        int next[maxn];
        char st[maxn],pt[maxn]; ///先数组存 主串 , 模式串
        while(cin>>st>>pt)
        {
            String s,p;  ///主串 , 模式串
    
            Creat(s);
            Creat(p);
    
            add(s,st);
            add(p,pt);
    
            getnext(p,next);
            kmp(s,p,next);
        }
        return 0;
    }


    如下图

     ↓  ↓ ↓ ↓当求next[4]时,前面绿色表示已经匹配,即a匹配   next[i]就等于j 也就是next[i-1]+1


     ↓  ↓ ↓ ↓同理 ,next[6]前面有 两个绿色表示已经匹配 next[i]=j (next[i-1]+1)

    next[i]失配 模式串(下面那个串)j=next[j],继续寻找匹配的位置......



     ↓  ↓ ↓ ↓同理 next[8]也如此求  next[]等于1 表示紧挨着前面没有匹配成功的  2 表示1个  以此类推..



    展开全文
  • 。。。
  • 数据结构KMP

    2019-03-04 13:38:21
    KMP主要用于字符串匹配,比如给一个长度为n的字符串s,然后再给一个长度为m的字符串t,问s中有没有连续子串和t一样(n&gt;=m) 显然,直接暴力求解,容易得到最坏O(m*(n-m))复杂度的算法。当这个朴素算法的...
  • 关于kmp算法,大家都非常熟悉,其涵义非常难懂,以至于我学习kmp算法的时候一直怀疑自己的智商,其具体思想,这里就不多说了,网上也有很多资料,我用的是严蔚敏老师的书,实现也是按说上的方法实现的,推荐大家把...
  • 数据结构-KMP 对模式串next数组的理解: 比如我们已经知道ababab,q=4时,next[4]=2(k=2,表示该字符串的前5个字母组成的子串ababa存在相同的最长前缀和最长后缀的长度是3,所以k=2,next[4]=2。这个结果可以理解成...
  • 数据结构KMP算法

    2020-07-10 23:31:16
    数据结构里面的KMP算法,这是在VC6.0里面边写的,上传的是一个工程,可以直接使用的
  • 数据结构关于KMP算法

    2016-11-13 12:13:34
    KMP 看了一天多的KMP终于有点眉目了,自己在本子总结的,希望以后自己翻起来的时候还能回忆起来。 下面是next的函数推导: 基本就是这些了 另外还有一些Java语言写的KMP程序: package dataStructure;   ...
  • KMP算法是一种模式串匹配算法,即在主串S中找到模式串T第一次出现的首个字符在主串中的位置的一种相对高效的算法。为什么说KMP相对高效,这是因为在蛮力(BF)算法中如果当i!=j时,不仅仅j(模式串指针) 需要回退到...
  • 数据结构——KMP算法

    2018-08-06 18:10:16
    1.什么是模式匹配   自己看看百度百科,模式匹配、简单模式匹配 ... ...2.模式匹配的KMP算法的优点 ... KMP算法是对简单模式匹配算法的改进,简单模式匹配算法,每次模式串(子串)匹配不同时,模式...
  • 数据结构_KMP

    2016-03-27 20:27:01
    数据结构KMP算法的实现
  • 数据结构】 串 KMP算法实现 KMP算法应用于串的模式匹配中 普通模式匹配算法在进行匹配时需要频繁对主串指针进行回溯,KMP算法通过将模式向右滑动一段距离的方式避免了主串的回溯,同时降低了算法复杂度 ,由...
  • 最近老被KMP 算法给烦着,几经思考加探索加画图加验证加分析,终于在我的努力下,发现了书中一个重大的问题,它里面的KMP函数是化简了的,也就是说书上的解释 与 函数 是不完全对应的,这可苦了那些绞尽脑汁苦苦思索...
  • 数据结构--KMP算法

    2018-01-22 11:06:07
    要完善一个String字符串类,那么实现查找子串的功能是必不可少的,实现子串查找可以使用朴素算法,每次匹配一个字符后向右移动一个位置,这样执行下来效率是比较低的,所以就有了KMP算法,它能够准确的知道当前字符...
  • KMP算法数据结构课上讲了两天,还是晕晕乎乎的,先把《算法笔记》里的笔记放上来吧~以后想起来再看 笔记文件过大,出不来可以先等等 笔记很占服务器带宽,访问速度应该挺慢的~ ...
  • 求 子串 的 位置 有两种方法,一种是暴力搜索法,另一种就是KMP 算法。他们的效率 在一般的情况下,区别不大。但是在 串的 变化 范围特别小的情况下,例如 只有 0 和 1,KMP 的时间复杂度是 O(m+n),而暴力搜索法定...
  • // KMP字符串模式匹配算法 // 输入: S是主串,T是模式串,pos是S中的起始位置 // 输出: 如果匹配成功返回起始位置,否则返回-1 int KMP(PString S, PString T, int pos) { assert(NULL != S); assert(NULL != T); ...
  • 串这一节在大一学数据结构时老师并没有着重讲解,只让我们会求一个字符串的next数组就行了,这次学习的时候认真看了下,也花了挺长时间的,好好总结一下: 1、串的匹配是串的基础同时也非常重要的操作,最初人们用...
1 2 3 4 5 ... 20
收藏数 15,464
精华内容 6,185
关键字:

kmp 数据结构