kmp算法数据结构

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;

}

收起

展开全文

c语言

C/C++/Java代码模式匹配算法 KMP算法数据结构【经典算法思想】详解

2018-09-10 16:18:51

什么是模式匹配、常见模式匹配算法及C/C++/Java代码　详见...KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KM...

什么是模式匹配、常见模式匹配算法及C/C++/Java代码　详见：https://blog.csdn.net/kjcxmx/article/details/82348917

KMP算法是什么？

先看看某度的解释。。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

KMP算法的核心，也就是为什么可以如此的高效？关键就在于它Next数组的存在，有了Next数组就好比有一个滑动窗口，这样就避免了在匹配过程的主串中元素下标 i 不会发生回溯，也就是比较过程中的 i 始终是增加或不变的，这样就使得时间复杂度降低了，效率大大提高。

如下例子：主串T为“BABABCAB”，模式串S为“ABCA”。



A、见下图KMP.1开始进行Next数组的计算，首先把模式串S进行标号。（下面的例子中下标是从0开始的）



B、见下图KMP.2中，分别写出每个字串的对应前缀，（当然也可以不写出，熟悉之后直接计算即可）,最后一行也就是5号“A”对应的前缀为整个模式串。



C、见下图KMP.3分别对各个子串的前后缀比较，算出最长字串的长度，写在对应左侧。如下文字分析

第一行，只有一个字符“A”，没有前缀和后缀（前缀和后缀不能为串本身），所以为0

第二行，串为“A B”，前缀为“A”，后缀为“B”，不匹配（一致），所以为0

第三行，串为“A B A”，前缀为“A”和“A B”，后缀为“A”和“B A”，最大匹配长度为“A”=="A"，所以为1

第四行，串为“A B A B”，前缀为“A”和“A B”和“ABA”，后缀为“B”和“A B”和“BAB”，最大匹配长度为“A B”=="AＢ"，所以为２

第五行，串为“A B AＢＣ”，前缀为“A”和“A B”和“ABA”和“ABAB”，后缀为“Ｃ”和“B AＢＣ”和“ＡＢＣ”和“BC”均不匹配，所以为０

第六行，串为“A B AＢＣＡ”，前缀为“A”和“A B”和“ＡＢＡ”和“ＡＢＡＢ”和“ＡＢＡＢＣ”，后缀为“Ａ”和“ＣＡ”和“ＢＣＡ”和“ＡＢＣＡ”和“ＢＡＢＣＡ”，最大匹配长度为“A”=="A"，所以为1



得出最大前后缀长度
	子串
			Ａ
			ＡＢ
			ＡＢＡ
			ＡＢＡＢ
			ＡＢＡＢＣ
			ＡＢＡＢＣＡ
		
前缀
			 
			Ａ
			Ａ、Ｂ、ＡＢ
			Ａ、ＡＢ、ＡＢＡ
			Ａ、ＡＢ、ＡＢＡ、ＡＢＡＢ
			Ａ、ＡＢ、ＡＢＡ、ＡＢＡＢ、ＡＢＡＢＣ
		
后缀
			 
			Ｂ
			Ｂ、Ａ、ＢＡ
			Ｂ、ＡＢ、ＢＡＢ
			Ｃ、ＢＣ、ＡＢＣ、ＢＡＢＣ
			Ａ、ＣＡ、ＢＣＡ、ＡＢＣＡ、ＢＡＢＣＡ
		
最大
			 
			 
			Ａ、Ｂ
			ＡＢ
			 
			Ａ
		
最大长度
			０
			０
			１
			２
			０
			１
		
D、见下图KMP.４我们得到了一个数列“００１２０１”，并不是我们的Next数组，把这个数列不妨叫做ＭLength，对应写在子串下面。



E、见下图KMP.５我们将ＭLength中最后一个元素即“１”删除，在开头增加一个元素“－１”，然后将整个ＭLength加一，即得到Next数组“０１１２３１”。到此我们便得到了Next数组，下面给出代码



Java代码：

    /**
     * 获取next数组的值
     * @param ps 模式串(匹配串)
     * @return 
     */
    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]) { //判断是否匹配
               next[++j] = ++k;
           } else {
               k = next[k];
           }
        }
        return next;
    }

Ｃ／Ｃ＋＋代码：

void GetNext(char* p,int next[]){  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1) {  
        if (k == -1 || p[j] == p[k]) {  //p[k]表示前缀，p[j]表示后缀  
            ++k;  
            ++j;  
            next[j] = k;  
        } else{  
            k = next[k];  
        }  
    }  
}  

 

优化KMP算法：

其实上面的方法求Next数组，有一定的缺陷，匹配不成功有时候需要将模式串的ｊ回溯。所以对于已经匹配过的了，就不必再重新回到开头重新匹配了。

A、见下图KMP.６我们将在图KMP.５中修改，新增一行，分为两步给出NextVal数组。首先将第一个元素填为０

如果ＭLength［ｊ］！＝Next［ｊ］，则对应的填入Next中的数值
	如果ＭLength［ｊ］＝＝Next［ｊ］，则对应的填入ｊ－１对应的序号中的Next数值（这句话比较绕，多想想）这里的ｊ是大于１的，即为ｊ＞１.这就解释了为什么首元素置零了。图中标的挺清楚，对应的符号一块看。


给出下面代码：

Java代码：

    /**
     * 优化后的获取next数组的值
     * @param ps 模式串(匹配串)
     * @return 
     */
    public static int[] getNextVal(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]) { //增加了一层判断，当两个字符相等时要跳过，否则赋值为k
                  next[j] = next[k];
               } else {
                  next[j] = k;
               }
           } else {
               k = next[k];
           }
        }
        return next;
    }

Ｃ／Ｃ＋＋代码：

void GetNextval(char* p, int next[]) {  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1) {  
        if (k == -1 || p[j] == p[k]) { //p[k]表示前缀，p[j]表示后缀  
           ++j;  
           ++k;  
　　　　　　if (p[j] != p[k]) //只需要改动在下面4行，添加一步判断  
                next[j] = k;  
           else
           　　　next[j] = next[k];  
        } else {  
            k = next[k];  
        }  
    }  
}

KMP算法：

Java代码：

    /**
     * 经典KMP算法
     * @param ts 主串(目标串)
     * @param ps 模式串(匹配串)
     * @return 
     */
    public static int KMPSearch(String ts, String ps) {
        char[] t = ts.toCharArray();
        char[] p = ps.toCharArray();
        int i = 0; // 主串的位置
        int j = 0; // 模式串的位置
        int[] next = getNext(ps);
        while (i < t.length && j < p.length) { //主要是这个循环
           if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，j也要归0
               i++;
               j++;
           } else {
               // i不需要回溯 i = i - j + 1;
               j = next[j]; // j回到指定位置
           }
        }
        if (j == p.length) {
           return i - j;
        } else {
           return -1;
        }
    }

Ｃ／Ｃ＋＋代码：

int KmpSearch(char* s, char* p) {  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen) {     
        if (j == -1 || s[i] == p[j]){//j = -1，或当前字符匹配成功（即S[i]==P[j]）则后移
            i++;  
            j++;  
        } else {        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

结语：

这样就完成了著名的KMP算法，算法中重要的是算法所蕴含的思想，理解了具体的算理也就能迁移到其他方面了。

得出最大前后缀长度
子串	Ａ	ＡＢ	ＡＢＡ	ＡＢＡＢ	ＡＢＡＢＣ	ＡＢＡＢＣＡ
前缀		Ａ	Ａ、Ｂ、ＡＢ	Ａ、ＡＢ、ＡＢＡ	Ａ、ＡＢ、ＡＢＡ、ＡＢＡＢ	Ａ、ＡＢ、ＡＢＡ、ＡＢＡＢ、ＡＢＡＢＣ
后缀		Ｂ	Ｂ、Ａ、ＢＡ	Ｂ、ＡＢ、ＢＡＢ	Ｃ、ＢＣ、ＡＢＣ、ＢＡＢＣ	Ａ、ＣＡ、ＢＣＡ、ＡＢＣＡ、ＢＡＢＣＡ
最大			Ａ、Ｂ	ＡＢ		Ａ
最大长度	０	０	１	２	０	１

收起

展开全文

模式匹配

C/C++/Java代码朴素的(暴力法)模式匹配算法 KMP算法数据结构

2018-09-04 09:23:55

串的模式匹配KMP算法：https://blog.csdn.net/kjcxmx/article/details/82587924 什么是模式匹配、常见模式匹配算法及C/C++/Java代码　详见：https://blog.csdn.net/kjcxmx/article/details/82348917 算法思想： ...

朴素的模式匹配(暴力法)算法

串的模式匹配KMP算法：https://blog.csdn.net/kjcxmx/article/details/82587924

什么是模式匹配、常见模式匹配算法及C/C++/Java代码　详见：https://blog.csdn.net/kjcxmx/article/details/82348917

算法思想：

从目标串的的第一个字符起与模式串的第一个字符比较，若相等，则继续对字符进行后续的比较，否则目标串从第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。  

某度的解释：

若模式子串的长度是m,目标穿的长度是n，这时最坏的情况是每遍比较都在最后出现不等，即没变最多比较m次，最多比较n-m+1遍，总的比较次数最多为m(n-m+1)，因此朴素的模式匹配算法的时间复杂度为O(mn)。朴素的模式匹配算法中存在回溯，这影响到匹配算法的效率，因而朴素的模式匹配算法在实际应用中很少采用。在实际应用主要采用无回溯的匹配算法，KMP算法和BM算法均为无回溯的匹配算法。

如下例子：主串T为“BABABCAB”，模式串S为“ABCA”。



A、见下图BF.1开始第一步的匹配，i = 0，j = 0时（从0开始的），主串的值不等于模式串的值，则进行下一步，也就是 j++而也相应i++。 



B、见下图BF.2开始第二步的匹配，T[1] = S[0]，所以第一个字符是匹配的，那么将进行第二个字符的验证，也就是 j++而也相应i++。



C、见下图BF.3开始第二步的匹配，T[2] = S[1]，所以S中第二个字符也是匹配的，那么将进行S中第三个字符的验证，也就是 j++而也相应i++。



D、见下图BF.4开始第三步的匹配，T[3] ！= S[3]，所以S中第三个字符是不匹配的，那么将进行回溯，就是一下回到开始的位置，之前匹配的S[0]和S[1]的结果无效了。所以对于i来说赋值为i = 2，对应的j 将返回为j = 0,重复第A、B、C、以上步骤，这里省略。



E、见下图BF.5开始匹配，T[6] = S[3]，所以S中第四个字符也是匹配的，因为模式串S结束，所以将匹配成功。



E、如果模式串为S="AAAA",则不会匹配成功，那么将会返回-1，匹配失败，对于时间复杂度来讲就是最坏情况。

C代码：

#include <stdio.h>
#include <string.h>

int  index (char S[],char T[]){
     int  lenS,lenT;
     int  i=1,j=1; //注意，这里是从开始的，图解为从0开始
     lenS=strlen(S)-1;//主串S实际长度
     lenT=strlen(T)-1;//子串T实际长度

     while ( i<=lenS && j<=lenT ){
        if ( S[i] == T [j] ){//若两字符相等，对应+1
            ++i;
            ++j;
        }else{
            i=i-(j-1)+1; //主串回到上次匹配的下一位
            j=1; //子串从头开始匹配，开始设置为1为开始
        }
     }
    if ( j>lenT ){
    	return i-lenT;
    }else{
    	return -1;
    }
    
}
int main(){
    char T[]=" abcdabcdeabcdef";
    char S[]=" abcdef";
    int pos; //位置
    pos = index(T,S);
    printf("%d",pos);
    return 0;
}

C++代码：

#include <iostream>
#include <string>
using namespace std;
using std::string;
 
int BruteForce(string Text, string Pattern){
	int lenT = Text.length();
	int lenP = Pattern.length();

	int s,i;
	for (s = 0; s <= lenT-lenP; s++){
		i = 0;
		bool bEqual = true;
		while (bEqual && (i < lenP)){
			if (Text[s+i] == Pattern[i]){
				i++;
			}else{
				bEqual = false;
			}
		}
		if (bEqual){
			return s;
		}
	}
	return -1;
}

int main (){
	string T = "abcdabcdeabcdef";
	string S = "abcde";
	int result = BruteForce(T,S);
	cout << result;
	return 0;
}


Java 代码：

    /**
     * 暴力法求解(朴素模式匹配)
     * @param ts 主串(目标串)
     * @param ps 模式串(匹配串)
     * @return 
     */
    public static int bruteForce(String ts, String ps) {
        char[] t = ts.toCharArray();
        char[] p = ps.toCharArray();
        int i = 0; // 主串的位置
        int j = 0; // 模式串的位置
        while (i < t.length && j < p.length) {
           if (t[i] == p[j]) { // 当两个字符相同，就比较两者的下一个
               i++;
               j++;
           } else {
               i = i - j + 1; // 若不匹配，则i后退回溯，就是这一步增加了复杂度
               j = 0; // j赋值为0
           }
        }
        if (j == p.length) {
           return i - j;
        } else {
           return -1; //匹配失败，返回-1
        }
    }

 

其实这个算法是比件容易理解的，只要理解了算法的思想就好，但这种算法对于时间复杂度要求较高，一般不推荐，尤其是数据量较大时，影响算法效率，增大不必要的开销。

收起

展开全文

模式匹配

js实现kmp算法_数据结构作业之完整KMP算法实现通讯录

2020-12-30 19:57:25

对于本文的KMP算法，你需要看看这些文章《数据结构作业之串实现通信录》《KMP算法之next数组的简便求解》。另外，对于本文的代码，是摘抄自书上的，没有什么可讲的，要是不懂的话，自己看数据结构的书来理解吧。先看...

对于本文的KMP算法，你需要看看这些文章《数据结构作业之串实现通信录》《KMP算法之next数组的简便求解》。另外，对于本文的代码，是摘抄自书上的，没有什么可讲的，要是不懂的话，自己看数据结构的书来理解吧。
先看看实现：
代码：
#include "iostream"
#include "windows.h"
using namespace std;
typedef struct
{
char str[60];
int length;
}SeqString;
void StrAssign(SeqString *s, char cstr[])
{
int i=0;
for (;cstr[i]!='\0'; i++)
{
s->str[i]=cstr[i];
}
s->length=i;
}
int GetNext(SeqString T, int next[])
{
int j=0;
int k=-1;
next[0]=-1;
while (j
{
if (k==-1 || T.str[j]==T.str[k])
{
j++;
k++;
next[j]=k;
}
else
{
k=next[k];
}
}
return 1;
}
int KMP_Index(SeqString S,int pos, SeqString T, int next[])
{
int i,j;
i=pos-1;
j=0;
while (i
{
if (j==-1 || S.str[i]==T.str[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if (j>=T.length)
{
return i-T.length+1;
}
else
{
return -1;
}
}
int StrLength(SeqString s)
{
return s.length;
}
int main()
{
SeqString s,t;
int find,num;
int next[40];
char tongxunlu[10][40];
char chazhao[40];
cout<
cout<
cout<
cin>>num;
cout<
cout<
for (int i=0; i
{
cin>>tongxunlu[i];
}
cout<
cout<
cin>>chazhao;
for (int i=0; i
{
StrAssign(&s,tongxunlu[i]);
StrAssign(&t,chazhao);
GetNext(t,next);
find=KMP_Index(s,1,t,next);
if (find > 0)
{
cout<
cout<
}
}
system("pause");
return 0;
}

收起

展开全文

js实现kmp算法_数据结构：KMP算法
2020-12-29 05:25:10
推荐Bilibili讲解视频：BV1jb411V78H推荐csdn讲解文章：https://www.cnblogs.com/JoBlg/p/4087230.html?tdsourcetag=s_pctim_aiomsgKMP算法起源于模式串与主串的匹配问题。例如下面这个例子，要想在主串中寻找到模式...
收起
【数据结构】kmp算法笔记
2019-09-20 12:48:42
KMP算法数据结构课上讲了两天，还是晕晕乎乎的，先把《算法笔记》里的笔记放上来吧~以后想起来再看笔记文件过大，出不来可以先等等笔记很占服务器带宽，访问速度应该挺慢的~ ...
收起
算法
严蔚敏数据结构kmp算法详解_数据结构与算法pdf下载
2020-09-15 18:55:10
4.3.2 KMP 算法 KMP 算法是 D.E.Knuth J.H.Morris 和 V .R.Pratt 共同提出的 , 简称 KMP 算法该算法较 BF 算法有较大改进 , 主要是消除了主串指针的回溯 , 从而使算法效率有了某种程度的提高所谓真子串是指模式...
收起
数据结构之KMP算法
2020-03-08 12:18:39
数据结构KMP算法代码，并对KMP算法进行了改进优化，注释详细，易于理解，并附带举例说明。。。。。。
收起
数据结构与算法之KMP算法
2021-01-17 23:59:58
数据结构与算法系列 数据结构与算法之哈希表 ...数据结构与算法之KMP算法 目录数据结构与算法系列数据结构与算法之哈希表数据结构与算法之跳跃表数据结构与算法之字典树数据结构与算法之2-3树数据结构与算法之平衡二叉.
收起
字符串 java
KMP算法基础知识，数据结构
2020-12-28 11:24:09
KMP算法基础知识，数据结构
收起
js实现kmp算法_数据结构与算法JavaScript (五) 串(经典KMP算法)
2020-12-21 16:37:47
KMP算法和BM算法KMP是前缀匹配和BM后缀匹配的经典算法，看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同前缀匹配是指：模式串和母串的比较从左到右，模式串的移动也是从左到右后缀匹配是指：模式串和母...
收起
数据结构KMP算法
2013-11-21 09:52:39
数据结构里面的KMP算法，这是在VC6.0里面边写的，上传的是一个工程，可以直接使用的
收起
数据结构与算法--KMP算法 一步一步带你用Python实现KMP算法 Python实现KMP算法
2020-01-08 17:38:05
一步一步带你用Python实现KMP算法
收起
字符串算法 python
数据结构 KMP算法
2021-01-20 14:51:21
1、KMP算法的用途 KMP算法是用来找出a字符串中的b字符串，其中a叫做文本串，b叫做模式串 KMP算法是如何在a文本串中找出b模式串的呢？如图所示：当将模式串与文本串一一进行对比时，如果出现匹配不上的情况时，...
收起
数据结构_KMP算法与KMP算法的优化
2021-01-02 15:44:34
KMP算法 主串指针不回溯，只有模式串指针回溯。所以不同的模式串对应不同的表。观察：求模式串的next数组。 next数组：当模式串的第j个字符匹配失败时，令模式串跳到next[j]再继续匹配。串的前缀：包含第一个...
收起
【数据结构与算法】KMP算法
2020-06-24 00:02:22
KMP算法的前身---暴力破解法2.KMP算法的实现2.1 KMP算法的思路2.2 对模式串特征的描述2.3 next数组含义2.4 next数组的求法2.5 实现next表的创建2.6 KMP算法的实现2.7 KMP算法总结3.KMP算法的优化3.1 KMP算法的问题...
收起
字符串
数据结构学习笔记- 基于链表的KMP算法
2020-02-14 17:05:43
基于链表的KMP算法 数据结构学习笔记模式串 pattern 需要匹配的串称为模式串需求分析查找首个与pattern匹配的子表 DoubleNode<T> search(DoublyList<T> pattern) 数据结构的声明 public class ...
收起
链表 java
算法与数据结构（KMP算法）
2020-12-04 14:34:38
字符串匹配算法KMP 如leetcode28题，求一个字符串是否和另一个字符串中的子串相匹配，如...KMP算法的核心就是寻找needle子串中是否存在相同的后缀与前缀并记录下来，记录的数组称为next数组，next[j]=k,表示pattern中
收起
数据结构-KMP算法
2020-03-16 23:28:27
KMP算法 KMP算法常用于字符串的模式匹配，KMP算法相对于朴素算法有了很大的改进，避免了没必要的回溯。该算法主要研究模式串，不需要主串的信息。 next数组：当模式匹配串T失配的时候，next 数组对应元素的...
收起
数据结构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 算法实现
2019-09-29 15:29:25
数据结构 KMP 算法实现 KMP 算法关键是要求出next数组下面是求next数组的算法 n利用next[0]= -1,…,next[i] 求next[i+1] 的算法：假设 k =next [i], 　１）若pk = pi, 则 p0… pi-k…pi 中最大相同前后缀长度...
收起
数据结构——KMP算法
2019-07-23 07:56:00
　KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配...
收起
js实现kmp算法_JavaScript中数据结构与算法(五)：经典KMP算法
2020-12-21 16:37:49
KMP算法和BM算法KMP是前缀匹配和BM后缀匹配的经典算法，看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同前缀匹配是指：模式串和母串的比较从左到右，模式串的移动也是从左到右后缀匹配是指：模式串和母...
收起
数据结构与算法-KMP算法
2020-09-08 11:08:18
KMP算法 KMP算法是一个解决模式串在文本串中是否出现过，如果出现过，找出最早出现位置的经典算法 Knuth-Morris-Pratt字符串查找法，简称“KMP”算法，这个算法由DonaldKunth, Vaughan Pratt, James H.Morris三人于...
收起
数据结构：BF算法 & KMP算法
2020-09-27 18:20:41
BF算法 KMP算法
收起
字符串
数据结构笔记-KMP算法
2020-11-06 17:59:56
字符串匹配算法在数据结构课本中可以看到BF(Brute Force)暴力求解，还有一种相对高效的一种算法KMP算法。博主研究KMP算法也有好几天了，在这过程中，有很多问题。去看别人的博客真的是看的一头雾水，很多文章的大体...
收起
数据结构KMP算法配图详解（超详细）
千次阅读 多人点赞 2020-02-18 22:02:42
KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练，但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂...
收起
字符串编程语言 c语言
JavaScript中数据结构与算法(五)：经典KMP算法
2020-10-24 01:36:23
主要介绍了JavaScript中数据结构与算法(五)：经典KMP算法,本文详解了KMP算法的方方面在,需要的朋友可以参考下
收起