精华内容
下载资源
问答
  • 数据结构 KMP

    2018-10-25 21:23:56
    思路二:根据字符串的查找理所当然想到KMPKMP的next数组,next[i]=k,从该字符串头结点开始的后k个结点与i结点往前k个字符串相同,很明显了。然后遍历再调整一下Getnext函数让其返回此次计算的最大值就行了。 #...

    题目:从一个字符串找到最长的重复字符串并返回第一个字符的位置。

    思路一:暴力,不做太多解释。

    思路二:根据字符串的查找理所当然想到KMP,KMP的next数组,next[i]=k,从该字符串头结点开始的后k个结点与i结点往前k个字符串相同,很明显了。然后遍历再调整一下Getnext函数让其返回此次计算的最大值就行了。

    #include <stdio.h>  
    #include <string.h>  
    #include <iostream>  
    #include <algorithm>
    #include <math.h>
    #include <map> 
    #include <queue>
    #include <vector> 
    #define PI acos(-1)
    #define INF 1e18
    #define inf 1e9
    #define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    #define Si(i) scanf("%d",&i)
    #define Pi(i) printf("%d\n",i);
    #define ElemType int 
    using namespace std ;
    typedef long long ll;
    typedef unsigned long long ull;
    const int _max = 10005;
    const ll mod = 1e9+7;
    char str[_max];
    int next[_max];
    int getNext(char *str,int *next){  
        int len=strlen(str);  
        int index=0;  
        int k=-1;  
        next[0]=k;  
        int max=0;  
        while(index<len){  
            if(k == -1 || str[index] == str[k]){  
                k++;  
                index++;  
                next[index]=k;  
                if(k>max)	max = k;
            }  
            else  
                k=next[k];  
        }
    	for(int i = 0 ; i < len ; i++)
    		cout<<next[i]<<' ';
    	cout<<endl;
        return max;  
    }  
      
    int main(){  
        while(cin>>str){
    	    int max=0;
    	    int nextMax;   
    	    int maxIndex;
    	    int len=strlen(str);   
    	    for(int index=0;index<len-1;index++){  
    	        nextMax=getNext(str+index,next); 
    	        if(nextMax>max){  
    	            max=nextMax;  
    	            maxIndex=index;  
    	        }  
    	    }  
    		cout<<maxIndex<<endl; 	
    		for(int i = 0 ; i < max ; i++)
    			cout<<str[maxIndex+i];
    		cout<<endl;
        }  
        
        return 0;  
    }  

     

    展开全文
  • 数据结构KMP实现

    2019-02-07 14:57:05
    数据结构KMP实现 代码如下: #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #define N 100 void cal_next( char * str, int * next, int len ) ...

    数据结构KMP实现

    代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define N 100
     
    void cal_next( char * str, int * next, int len )
    //next数组作用返回失配位之前的最长公共前后缀!; len为返回当前的最长公共前后缀长度
    {
        int i, j;
        next[0] = -1;
        for( i = 1; i < len; i++ )
        {
            j = next[ i - 1 ];
            while( str[ j + 1 ] != str[ i ] && ( j >= 0 ) )
            {
                j = next[ j ];
            }
            if( str[ i ] == str[ j + 1 ] )
            {
                next[ i ] = j + 1;
            }
            else
            {
                next[ i ] = -1;
            }
        }
    }
     
    int KMP( char * str, int slen, char * ptr, int plen, int * next )
    {
        int s_i = 0, p_i = 0;
     
        while( s_i < slen && p_i < plen )
        {
            if( str[ s_i ] == ptr[ p_i ] )
            {
                s_i++;
                p_i++;
            }
            else
            {
                if( p_i == 0 )
                {
                    s_i++;
                }
                else
                {
                    p_i = next[ p_i - 1 ] + 1;
                }
            }
        }
        return ( p_i == plen ) ? ( s_i - plen ) : -1;
    }
     
    int main()
    {
        char str[ N ] = {0};
        char ptr[ N ] = {0};
        int slen, plen;
        int next[ N ];
     
        while( scanf( "%s%s", str, ptr ) )
        {
            slen = strlen( str );
            plen = strlen( ptr );
            cal_next( ptr, next, plen );
            printf( "%d\n", KMP( str, slen, ptr, plen, next ) );
        }
        return 0;
    }
    
    

    运行结果如下:
    在这里插入图片描述
    欢迎您关注我的微信公众号:学习微站(studysth)在这里插入图片描述

    展开全文
  • 数据结构 KMP 算法实现 KMP 算法关键是要求出next数组下面是求next数组的算法 n利用next[0]= -1,…,next[i] 求next[i+1] 的算法: 假设 k =next [i],  1) 若pk = pi, 则 p0… pi-k…pi 中最大相同前后缀长度...

    数据结构 KMP 算法实现

    KMP 算法关键是要求出next数组下面是求next数组的算法

    n利用next[0]= -1,…,next[i] 求next[i+1] 的算法:

         假设 k =next [i],

       1) 若pk = pi, 则 p0… pi-k…pi 中最大相同前后缀长度为next[i+1] = k+1

      2)若pk ¹ pi ,置 k=next[k] ,然后转到 第1步.

        (设 k = next[k],就是考虑前一个更短的匹配前缀,从那里继续向下检查)

      3)若 k 值(来自next)为-1,就得到p0… pi-k…pi中最大相同前后缀的长度为k = 0(即next [i+1] = 0)

    对求next数组的改进

      n当 pi !=  tj 时,若pi == pk, 那么一定有 pk != tj .所以模式串应再向右移 k-next[k]位,下一步用 pnext[k] 与tj比较
      n对于next[i]=k 的改进:
    if  (pk== pi)  
        next[i] = next[k];
    else  
        next[i]=k;

      这一改进可以避免一些不必要的操作.

     

    下面是一个例子:

     1 /*============================================================================*\
     2  *
     3  *                     数据结构基础练习
     4  * 
     5  *                        KMP 算法测试 
     6  * 
     7  *                    2013-05-20 by 樊列龙 
     8  *
     9 \*============================================================================*/
    10 
    11 #include <iostream>
    12 
    13 using namespace std;
    14 
    15 void set_next(char* p, int* next)
    16 {
    17     int i = 0, j= -1;
    18     next[0] = -1;
    19     
    20     while(p[i])
    21     {
    22         while(j >= 0 && p[i] != p[j])
    23         {
    24             j = next[j];
    25         }
    26         i++,j++;
    27         if(p[i] == p[j]) next[i] = next[j];
    28         else next[i] = j;
    29         
    30     }
    31 }
    32 
    33 int KMP(char* s, char* p, int *next, int n)
    34 {
    35     int i = 0,j = 0;
    36     int count = 0;
    37     while(s[i] && j < n)
    38     {
    39         if(j == -1 || s[i] == p[j])
    40         {
    41             j++,i++;
    42             count++;
    43         }
    44         else
    45         {
    46             j = next[j];
    47         }
    48     }
    49     
    50     if(j >= n)
    51     {
    52         return i-n+1;
    53     }
    54     
    55     return 0;
    56 }
    57 
    58 int main()
    59 {
    60     char s[] = "abaabca8934baaabaabc23abaabcaca2312";
    61     char p[] = "abaabcac";//8个字符 
    62     int next[100];
    63 
    64     set_next(p,next);
    65     cout << KMP(s,p,next,sizeof(p)-1) << endl;
    66     
    67     return 0;
    68 }

    结果:

    23
    

      

     

     

    转载于:https://www.cnblogs.com/CocoonFan/archive/2013/05/20/3087913.html

    展开全文
  • 上回说到数据结构-KMP算法,那么今天小编就带着相关真题来啦!(2015统考真题)已知字符串s为“abaabaabacacaabaabcc”,模式串t为“abaabc5’。采用KMP算法进行匹配,第一次出现“失配”(s[i]≠t[j])时,i=j=5,则...

    12e84d75790bb54a7cce9cdbf7d03908.png

    上回说到数据结构-KMP算法,那么今天小编就带着相关真题来啦!

    (2015统考真题)已知字符串s“abaabaabacacaabaabcc”,模式串t“abaabc5’。采用KMP算法进行匹配,第一次出现失配”(s[i]≠t[j])时,i=j=5,则下次开始匹配时,ij的值分别是(   )。

    A.i=1j=0                        B.i=5j=0

    C.i=5j=2                        D.i=6j=2

    解:

    首先要计算出模式串t的next数组

    j

    0

    1

    2

    3

    4

    5

    P[j]

    a

    b

    a

    a

    b

    c

    next[j]

    -1

    0

    0

    1

    1

    2

    第一躺匹配时i=5j=5失败:

    s: a  b  a  a  b  a  a  b  a  c  a  c  a  a  b  a  a  b  c  c

    t: a  b  a  a  b  c

    第二趟开始匹配时应该如下所示,可见i=5j=2:

    s: a  b  a  a  b  a  a  b  a  c  a  c  a  a  b  a  a  b  c  c

    t:          a  b  a  a  b  c

    答案为:C

    更多考研福利关注“计算机考研研究院”公众号点击“资料下载”即可拥有!

    467a2e39957e8b922633d5dcd5afb339.png

    72ca64b9aeb621192fc98a0e1677e2c9.gif

    ☀22研友加:1071300584

    ☀21研友加:723214845

    230bb9befe5a815b0257cdc33fc98457.png

    99df54f58d4c5efb397c72f10297854e.gif57523fd19574db68e408a96ddfbdc20d.gif

    ●考研计算机 | 数据结构—结构算法

    ●考研计算机 | 数据结构—研究内容

    ●考研计算机 | 数据结构—物理结构

    ●考研计算机 | 总线

    7200e70de919efc76e8b7370554f009c.png确认过眼神你是我爱的人更多考研资讯  关注我们就对了228e5ae88e22394090ece721a8b83f7a.png30c2f5ce77866fabfac705120f8b9650.png扫码关注我们ef17629931152087dda3b73a490a4a86.gif

    展开全文
  • 数据结构KMP算法

    2013-11-21 09:52:39
    数据结构里面的KMP算法,这是在VC6.0里面边写的,上传的是一个工程,可以直接使用的
  • 4.3.2 KMP 算法 KMP 算法是 D.E.Knuth J.H.Morris 和 V .R.Pratt 共同提出的 , 简称 KMP 算法该算法较 BF 算法有较 大改进 , 主要是消除了主串指针的回溯 , 从而使算法效 率有了某种程度的提高 所谓 真子串 是指模式...
  • 数据结构 KMP算法

    2021-01-20 14:51:21
    1、KMP算法的用途 KMP算法是用来找出a字符串中的b字符串,其中a叫做文本串,b叫做模式串 KMP算法是如何在a文本串中找出b模式串的呢? 如图所示:当将模式串与文本串一一进行对比时,如果出现匹配不上的情况时,...
  • 数据结构KMP算法配图详解(超详细)

    千次阅读 多人点赞 2020-02-18 22:02:42
    KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂...
  • 数据结构KMP算法例题

    2020-03-23 19:59:23
    今天遇到一个数据结构的问题,索性就把KMP算法的题总结一下,有不对的地方希望指正。 串“ababaabab”的nextval为( A)。 A.010104101 B.010102101 C.010100011 D.010101011 ①i从0开始 方法一: 第0位:Next[0]...
  • 拓展三 ...KMP算法 #include <stdio.h> typedef char* String; void get_next(String T,int *next) { int j=0; int i=1; next[1]=0; while(i<T[0]) { if(0==j || T[i]==T[j]) ...
  • CUP 数据结构KMP学习

    2018-10-14 17:18:06
    #include &lt;iostream&gt; #include &lt;string&gt; #include &lt;cstdio&gt; #define Max_Size 100005 int p_next[Max_Size]; using namespace std; int compare(string s_ , ... ...
  • 数据结构KMP&BF算法

    2019-10-28 20:42:34
    串的匹配算法广泛应用在现在的很多方面,这里讲一下BF算法和KMP算法(重点)。 一、BF算法,其原理就是循环进行比较,字符相同则下标都加一,不同主串回到i+1,子串回到1,重新匹配。 算法如下: /*BF算法*/ int...
  • 我做这个视频是为了能够帮助一些不懂 kmp 算法的小伙伴们理解,kmp 算法的思想, 以及最关键的 kmp next 数组代码的含义,顺便也帮自己梳理下对 kmp 的理解。 总觉得处处都是巧合,但其实都是必然的。 kmp 算法进行...
  •  之前对kmp算法虽然了解它的原理,即求出P0···Pi的最大相同前后缀长度k;但是问题在于如何求出这个最大前后缀长度呢?我觉得网上很多帖子都说的不是很清楚,总感觉没有把那层纸戳破,后来翻看算法导论,32章 ...
  • https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
  • 下面是导图的目录结构:不要小看这张导图(这可是武功秘籍,秘籍已经有了,好好练,神功指日可待),只要你跟着这个导图去复习数据结构与算法,里面的知识点都搞透彻,面试数据结构问题基本难不倒你了。这么好的东西都...
  • 根据KMP算法的next数组值,推断模式字符串。 假设模式字符串中只存在0,1两种字符。给出首字符和next数组。请输出模式字符串。如果next数组不合法则输出ERROR Input Format 先输入模式字符串首字符0或者1,然后输入...
  • 总结一下今天的收获(以王道数据结构书上的为例子,虽然我没看它上面的。。。):其中竖着的一列值是模式串前缀和后缀最长公共前缀。 最后求得的结果符合书上的结果,如果是以-1开头的话就不需要再加1,如果是以0...
  • 课程名称:数据结构 实验项目名称:串基本操作的实现 实验目的: 1.掌握串的模式匹配操作。 实验要求: 1、 分别使用BF和KMP算法完成串的模式匹配。 实验过程: 1、 设计完成next值的计算函数; 2、 ...
  • 数据结构 KMP算法代码

    千次阅读 2014-03-28 13:25:50
    //匹配字符串模式值  void getFail(char P[],int f[]) { int m=strlen(P); f[0]=0; f[1]=0; for(int i=1;i { int j=f[i]; while(j&&P[i]!=P[j])  j=f[j]; f[i+1] =P[i]==P[j] ? j+1:0;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,161
精华内容 1,264
关键字:

数据结构kmp

数据结构 订阅