精华内容
下载资源
问答
  • 数据结构实验之串一: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算法 数据结构

    2017-05-18 15:24:56
    KMP算法的实现

    kmp.h

    文件的建立

    typedef int Status;
    #define MAXSTRLEN 255
    typedef struct 
    {
    char data[MAXSTRLEN+1];
    int length;
    }HString;


    Status Concat(HString &T,HString S1,HString S2);
    void StrAssign(HString &S,char cstr[]);
    Status StrCopy(HString &T,HString S);
    Status StrEmpty(HString S);
    Status StrCompare(HString S,HString T);
    Status StrLength(HString S);
    Status ClearString(HString &S);
    Status Concat(HString &S);
    Status SubString(HString &Sub,HString S,int pos,int len);
    int Index(HString S,HString T);
    Status Replace(HString &S,HString T,HString V);
    Status StrInsert(HString &S,int pos,HString T);
    Status StrDelete(HString &S,int pos,int len);
    Status DestroyString(HString &S);
    Status Index_KMP(HString S,HString T);
    void get_nextval(HString T,int nextval[]);
    void DispStr(HString s);
    void get_next(HString T,int next[]);
    Status Index_KMP1(HString S,HString T);


    KMPS.cpp 文件的建立



    #include "stdafx.h"
    #include "kmp.h"




    Status Concat(HString &T,HString S1,HString S2)
    {
    int i,uncut;
    if(S1.length+S2.length<=MAXSTRLEN)
    {
    T.length=S1.length+S2.length;
    for(i=1;i<=S1.length;i++)
               T.data[i]=S1.data[i];
    for(i=S1.length+1;i<=S1.length+S2.length;i++)
    T.data[i]=S2.data[i-S1.length];
    uncut=TRUE;
    }
    else if(S1.length<MAXSTRLEN)
    {
    for(i=1;i<=S1.length;i++)
    T.data[i]=S1.data[i];
            for(i=S1.length+1;i<=MAXSTRLEN;i++)
    T.data[i]=S2.data[i-S1.length];
    T.length=MAXSTRLEN;
    uncut=FALSE;
    }
    else
    {
            for(i=1;i<=MAXSTRLEN;i++)
    T.data[i]=S1.data[i];
    uncut=FALSE;
    }


    return uncut;
    }


    void StrAssign(HString &S,char cstr[])
    {

    int i;
    for (i=1;cstr[i-1]!='\0';i++)
    S.data[i]=cstr[i-1];
    S.length=i-1;
    }


    Status StrCopy(HString &T,HString S)
    {
    int i=0;
    T.length=S.length;
    while(S.data[i]!='\0')
    {
    T.data[i]=S.data[i];
    }
    return OK;
    }


    Status StrEmpty(HString S)
    {
    if(S.length==0&&S.data[1]=='\0')
    return TRUE;
    else
    return FALSE;
    }


    Status StrCompare(HString S,HString T)
    {
        
    return OK;
    }


    Status StrLength(HString S)
    {

    return S.length;
    }


    Status ClearString(HString &S)
    {
    int i;
    for(i=1;i<=S.length;i++)
    S.data[i]='\0';
    S.length=0;
    return OK;
    }


    Status Concat(HString T,HString S1,HString S2)
    {
    int i;
    T.length=S1.length+S2.length;
    for(i=1;i<=S1.length;i++)
               T.data[i]=S1.data[i];
    for(i=S1.length+1;i<=S1.length+S2.length;i++)
    T.data[i]=S2.data[i-S1.length];
    return OK;
    }


    Status SubString(HString &Sub,HString S,int pos,int len)
    {
    int i;
    for(i=pos;i<=len;i++)
    Sub.data[i-pos-1]=S.data[i];
    Sub.data[0]=len;
    return OK;
    }


    int Index(HString S,HString T)
    {
    int i=1,j=0;
    while (i<=S.length && j<T.length) 
    { if (S.data[i]==T.data[j])
    { i++;
    j++;
    }
    else
    { i=i-j+1;
    j=0;
    }
    }
    if (j>=T.length)
    return(i-T.length-1);
    else
    return(-1);
    }


    Status Replace(HString &S,HString T,HString V)
    {
        
    return OK;
    }


    Status StrInsert(HString &S,int pos,HString T)
    {
    int i;
        HString P;
    P.length=S.length+T.length;
    for(i=1;i<=pos-1;i++)
            P.data[i]=S.data[i];
    for(i=pos;i<=T.length;i++)
    P.data[i]=T.data[i-pos+1];
    for(i=pos;i<=S.length;i++)
    P.data[i+T.length]=S.data[i];
    for(i=1;i<=P.length;i++)
    S.data[i]=P.data[i];
    S.length=P.length;
    return OK;
    }


    Status StrDelete(HString &S,int pos,int len)
    {


    HString P;
    int i;
        P.length=S.length-len;
    for(i=1;i<=pos-1;i++)
            P.data[i]=S.data[i];
        for(i=pos+len;i<=S.length;i++)
    P.data[i-len]=S.data[i];
    return OK;
    }


    Status DestroyString(HString &S)
    {


    free(S.data);
    return OK;
    }


    Status Index_KMP(HString S,HString T)
    {
       int nextval[MAXSTRLEN+1];
       get_nextval(T,nextval);
       int i,j;
       j=1;
       i=1;
       while(i<=S.length&&j<=T.length)
       {
      if(j==0||S.data[i]==T.data[j])
      {
      ++i;
      ++j;
      }
      else 
      {
      
      j=nextval[j];
      }
       }
       if(j>T.length)
      return i-T.length;
       else 
      return 0;
    }


    void get_nextval(HString T,int nextval[])
    {
    int i,j;
    i=1;
    nextval[1]=0;
    j=0;
    while(i<T.length)
    {
    if(j==0||T.data[i]==T.data[j])
    {
    ++i;
    ++j;
    if(T.data[i]!=T.data[j])
    nextval[i]=j;
    else
    nextval[i]=nextval[j];
    }
    else 
    j=nextval[j];
    }
    }
    void DispStr(HString s)
    { int i;
    if (s.length>0)
    { for (i=1;i<=s.length;i++)
    printf("%c",s.data[i]);
    printf("\n");
    }
    }


    void get_next(HString T,int next[])
    {
       int i,j;
    i=1;
       next[1]=0;
       j=0;
       while(i<T.length)
       {
      if(j==0||T.data[i]==T.data[j])
      {
      ++i;
      ++j;
      next[i]=j;
      
      }
      else
      j=next[j];
       }
    }


    Status Index_KMP1(HString S,HString T)
    {
       int next[MAXSTRLEN+1];
       get_next(T,next);
       int i,j;
       j=1;
       i=1;
       while(i<=S.length&&j<=T.length)
       {
      if(j==0||S.data[i]==T.data[j])
      {
      ++i;
      ++j;
      }
      else 
      {
      
      j=next[j];
      }
       }
       if(j>T.length)
      return i-T.length;
       else 
      return 0;
    }

    主函数所在的文件

    #include "stdafx.h"
    #include "kmp.h"


    int main(int argc, char* argv[])
    {
    //printf("Hello World!\n");
    int j,a;
    int nextval[MAXSTRLEN+1],next[MAXSTRLEN+1];
    HString s,t;
    StrAssign(s,"abcabcdabcdeabcdefabcdefg");
    StrAssign(t,"abcdeabcdefab");
    printf("串s:");DispStr(s);
    printf("串t:");DispStr(t);


    get_nextval(t,nextval); //由模式串t求出nextval值
    get_next(t,next);
    printf("    j   ");
    for (j=1;j<=t.length;j++)
    printf("%4d",j);
    printf("\n");
    printf(" t[j]   ");
    for (j=1;j<=t.length;j++)
    printf("%4c",t.data[j]);
    printf("\n");


    printf("\n");
    printf(" nextval");
    for (j=1;j<=t.length;j++)
    printf("%4d",nextval[j]);
    printf("\n");
    printf("改进的KMP算法:\n");
    a=Index_KMP(s,t);
    printf("  t在s中的位置=%d\n",a);
    printf("<------------------------------------------------------------>\n");
    printf("    j   ");
    for (j=1;j<=t.length;j++)
    printf("%4d",j);
    printf("\n");
    printf(" t[j]   ");
    for (j=1;j<=t.length;j++)
    printf("%4c",t.data[j]);
    printf("\n");
    printf(" next   ");
    for (j=1;j<=t.length;j++)
    printf("%4d",next[j]);
    printf("\n");


    printf("旧版的KMP算法:\n");
    a=Index_KMP1(s,t);
    printf("  t在s中的位置=%d\n",a);
        system("pause");
    return 0;
    }

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

    2020-03-08 12:18:39
    数据结构KMP算法代码,并对KMP算法进行了改进优化,注释详细,易于理解,并附带举例说明。。。。。。
  • 数据结构 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

    2016-03-27 19:35:55
    数据结构KMP算法的实现

    今天下午实现了KMP算法


    这个算法算是奇妙,本机器看了10遍左右才基本理解

    算法的核心就是求出next,再依次根据next跳转,这样就能线性地匹配出字符串

    这里推荐一篇博文http://blog.csdn.net/joylnwang/article/details/6778316,joylnwang说得很好,深入浅出,只是在next数组是从1开始的,而pattern是从0起始,这也算是前几次学习的时候没有理解的地方

    今天下午写的代码也应用了template,也能兼容其他的数据类型,练习了一下C++

    <pre name="code" class="cpp">#include "iostream"
    #include "string"
    using namespace std;
    
    template <class T>
    class KPM
    {
    private:
    	int MAX_P;
    	int MAX_T;
    	int *next = new int[MAX_P + 1];
    	T	*pattern = new T[MAX_P + 1];
    	T	*target = new T[MAX_T];
    	int* BuildNext();
    public:
    	KPM(T *pat, int max_p, T *tar , int max_t)
    	{
    		MAX_P = max_p;
    		MAX_T = max_t;
    		pattern = pat;
    		target = tar;
    	}
    	int GetResult();
    };
    
    template <class T>
    int* KPM<T>::BuildNext()
    {
    	int i = 1;
    	int t = 0;
    	next[i] = 0;
    	while (i < MAX_P)
    	{
    		while (t > 0 && pattern[i - 1] != pattern[t-1])//依次向前找到next,确定f(t)
    		{
    			t = next[t];
    		}
    		++t;
    		++i;
    		if (pattern[i - 1] == pattern[t - 1])
    		{
    			next[i] = next[t];
    		}
    		else
    		{
    			next[i] = t;
    		}
    	}
    	for (int i = 1; i < MAX_P +1 ; i++)
    	{
    		cout << next[i] << " ";
    	}
    	cout << endl;
    	return next;
    }
    
    template <class T>
    int KPM<T>::GetResult()
    {
    	BuildNext();
    	int t = 0;
    	int p = 0;
    	while (t < MAX_T && p < MAX_P + 1)
    	{
    		if (p == 0 || target[t] == pattern[p - 1])
    		{
    			cout << target[t] << " " << t << " " << pattern[p] << " " << p << endl;
    			++t;
    			++p;
    		}
    		else
    		{
    			p = next[p];
    		}
    	}
    	if (p == MAX_P + 1)
    	{
    		cout << "从主串的第" << t - MAX_P + 1 << "个数开始匹配" << endl;
    		return t - MAX_P;
    	}
    	else
    	{
    		cout << "主串无可匹配的子串" << endl;
    		return 0;
    	}
    }
    
    int main()
    {
    	char *P = "abcabcacab";
    	char *T = "babcbabcabcaabcabcabcacabc";
    	KPM<char> *a = new KPM<char>(P, 10, T, 26);
    	a -> GetResult();
    	system("pause");
    }


    
    

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

    2013-11-21 09:52:39
    数据结构里面的KMP算法,这是在VC6.0里面边写的,上传的是一个工程,可以直接使用的
  • 数据结构- KMP

    2019-09-27 05:08:26
    数据结构 - KMP 引言 & 介绍 由于李总说过串这一章只讲一个KMP, 所以我这里也就只说一个KMP算法了 KMP算法, 说得简单点就是关键字搜索 一般方法 一般的关键字搜索的算法为: ...
  • KMP算法基础知识,数据结构
  • 数据结构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 ) ...
  • 4.3.2 KMP 算法 KMP 算法是 D.E.Knuth J.H.Morris 和 V .R.Pratt 共同提出的 , 简称 KMP 算法该算法较 BF 算法有较 大改进 , 主要是消除了主串指针的回溯 , 从而使算法效 率有了某种程度的提高 所谓 真子串 是指模式...
  • KMP基础 这是个KMP算法的裸题,没什么好说的主要是...数据结构实验之串三:KMP应用 :这题本来可以直接while循环嵌套写的,不过为了突出KMP的各个部分特地分开写了。 #include<stdio.h> #include<stdlib...
  • 数据结构 KMP算法

    2021-01-20 14:51:21
    1、KMP算法的用途 KMP算法是用来找出a字符串中的b字符串,其中a叫做文本串,b叫做模式串 KMP算法是如何在a文本串中找出b模式串的呢? 如图所示:当将模式串与文本串一一进行对比时,如果出现匹配不上的情况时,...
  • 上回说到数据结构-KMP算法,那么今天小编就带着相关真题来啦!(2015统考真题)已知字符串s为“abaabaabacacaabaabcc”,模式串t为“abaabc5’。采用KMP算法进行匹配,第一次出现“失配”(s[i]≠t[j])时,i=j=5,则...
  • 数据结构与算法系列 数据结构与算法之哈希表 ...数据结构与算法之KMP算法 目录数据结构与算法系列数据结构与算法之哈希表数据结构与算法之跳跃表数据结构与算法之字典树数据结构与算法之2-3树数据结构与算法之平衡二叉.
  • 数据结构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

    2018-08-29 01:10:03
    KMP主要用于字符串匹配,比如给一个长度为n的字符串s,然后再给一个长度为m的字符串t,问s中有没有连续子串和t一样(n&gt;=m) 显然,直接暴力求解,容易得到最坏O(m*(n-m))复杂度的算法。当这个朴素算法的...
  • 数据结构-KMP算法

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

    2020-12-26 00:15:42
    #include using namespace std; const int N=1e5+5,M=1e6+5; //数组注意不要越界 int n,m;...i++){ //kmp匹配过程 while(j&&s[i]!=p[j+1]) j=ne[j]; if(s[i]==p[j+1]) j++; if(j==n){ cout; j=ne[j]; } } return 0; }
  • 数据结构-KMP

    2020-08-14 19:47:57
    } } } int KMP(Str S, Str T) { int i = 1,j = 1; int next[T.length+1]; GetNext(T,next); while (i ) { //如果j = 0,或者当前字符匹配成功(即S[i] == T[j]),都令i++,j++ if (j == 0 || S.ch[i] == T.ch[j]) ...
  • ~~KMP数据结构

    2020-05-09 08:52:26
    模板 // s[]是长文本,p[]是模式串,n是s的长度,m是p的长度 求模式串的Next数组: for (int i = 2, j = 0; i <= m; i ++ ) { while (j &&...= p[j + 1]) j = ne[j];... if (p[i] == p[j + 1]) j ++ ;...
  • title: ‘字符串匹配:KMP’ date: 2019-10-16 17:50:39 ...description: JAVA数据结构与算法:字符串匹配之KMP 文章目录摘要简介详解最直接的回溯法KMP匹配图解KMP求解 next数组小结参考参考 摘要 ​ KM...
  • 数据结构——KMP算法

    2019-07-23 07:56:00
     KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
  • 数据结构笔记-KMP算法

    2020-11-06 17:59:56
    字符串匹配算法在数据结构课本中可以看到BF(Brute Force)暴力求解,还有一种相对高效的一种算法KMP算法。博主研究KMP算法也有好几天了,在这过程中,有很多问题。去看别人的博客真的是看的一头雾水,很多文章的大体...
  • 对于本文的KMP算法,你需要看看这些文章《数据结构作业之串实现通信录》《KMP算法之next数组的简便求解》。另外,对于本文的代码,是摘抄自书上的,没有什么可讲的,要是不懂的话,自己看数据结构的书来理解吧。先看...

空空如也

空空如也

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

kmp数据结构

数据结构 订阅