kmp算法代码

Ⅰ 数据结构中的KMP算法怎样用C实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define MAX_LEN_OF_STR 30 // 字符串的最大长度
typedef struct String // 这里需要的字符串数组,存放字符串及其长度{
char str[MAX_LEN_OF_STR]; // 字符数组
int length;// 字符串的实际长度
}String, *PString;
// 得到字符串的next数组
void GetNextArray(PString pstr, int next[])
{assert(NULL != pstr); <br/>assert(NULL != next);<br/>assert(pstr->length > 0);// 第一个字符的next值是-1,因为C中的数组是从0开始的<br/>next[0] = -1;<br/>for (int i = 0, j = -1; i < pstr->length - 1; )<br/>{// i是主串的游标,j是模式串的游标// 这里的主串和模式串都是同一个字符串<br/> if (-1 == j || // 如果模式串游标已经回退到第一个字符<br/>pstr->str[i] == pstr->str[j]) // 如果匹配成功<br/> {// 两个游标都向前走一步<br/> ++i;++j;// 存放当前的next值为此时模式串的游标值<br/> next[i] = j;<br/> }else // 匹配不成功j就回退到上一个next值
{j = next[j];}}}
// KMP字符串模式匹配算法
// 输入: S是主串,T是模式串,pos是S中的起始位置
// 输出: 如果匹配成功返回起始位置,否则返回-1
int KMP(PString S, PString T, int pos)
{assert(NULL != S);<br/> assert(NULL != T);<br/> assert(pos >= 0);<br/> assert(pos < S->length);<br/>if (S->length < T->length)<br/> return -1;<br/>printf("主串\t = %s\n", S->str);<br/>printf("模式串\t = %s\n", T->str);<br/>int *next = (int *)malloc(T->length * sizeof(int));// 得到模式串的next数组<br/>GetNextArray(T, next);<br/>int i, j;<br/>for (i = pos, j = 0; i < S->length && j < T->length; ){// i是主串游标,j是模式串游标<br/> if (-1 == j || // 模式串游标已经回退到第一个位置<br/> S->str[i] == T->str[j]) // 当前字符匹配成功<br/> {// 满足以上两种情况时两个游标都要向前进一步<br/> ++i;++j;}
else // 匹配不成功,模式串游标回退到当前字符的next值
{j = next[j];}}
free(next);
if (j >= T->length)
{// 匹配成功
return i - T->length;}
else{// 匹配不成功
return -1;}}

Ⅱ c++数据结构KMP算法

#include <stdio.h>
#define N 9
#define M 8
typedef struct node
{ int i,j,v;
}JD;

int fast_transpos(JD ma[],JD mb[])
{ int n,col,p,k,t;
int num[M],cpot[M];
n=ma[0].j;
t=ma[0].v;
mb[0].i=n; mb[0].j=ma[0].i; mb[0].v=t;
if(t<=0)
return(0);
for(col=0;col<=n;col++)
num[col]=0;
for(p=1;p<=t;p++)
{ k=ma[p].j;
num[k]++;
}
cpot[0]=0; cpot[1]=1;
for(col=2;col<=n;col++)
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=t;p++)
{ col=ma[p].j;
k=cpot[col];
mb[k].i=ma[p].j;
mb[k].j=ma[p].i;
mb[k].v=ma[p].v;
cpot[col]++;
}
return(1);
}
void main()
{ JD ma[N]={{6,7,8},{1,2,12},{1,3,9},{3,1,-3},
{3,6,14},{4,3,24},{5,2,18},{6,1,15},{6,4,-7}};
JD mb[N];
int i;
fast_transpos(ma,mb);
for(i=0;i<N;i++)
printf("%d,%d,%d\n",mb[i].i,mb[i].j,mb[i].v);
}

Ⅲ KMP匹配算法

不懂得话，就自己跟上三四遍就好了，代码附上
有什么不懂的就问，不过还是尽量自己钻研的好
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
const int maxLen = 128;
class String
{
int curLen; //串的当前长度
char *ch; //串的存储数组
public:
String (const String & ob);
String (const char *init);
String ();
~String ()
{
delete [] ch;
}
int Length () const
{
return curLen;
}
String *operator () ( int pos, int len );
int operator == ( const String &ob )const
{
return strcmp (ch, ob.ch) == 0;
}
int operator != ( const String &ob ) const
{
return strcmp (ch, ob.ch) != 0;
}
int operator !() const
{
return curLen == 0;
}
String &operator = (const String &ob);
String &operator += (const String &ob);
char &operator [] (int i);
int fastFind ( String pat ) const;
//void fail (const char *T,int* &f);
void fail (int* &f);
};
String::String ( const String &ob ) //复制构造函数：从已有串ob复制
{
ch = new char[maxLen+1];
if ( !ch )
{
cout << "Allocation Error\n";
exit(1);
}
curLen = ob.curLen;
strcpy ( ch, ob.ch );
}
String::String ( const char *init ) //复制构造函数: 从已有字符数组*init复制
{
ch = new char[maxLen+1];
if ( !ch )
{
cout << "Allocation Error\n";
exit(1);
}
curLen = strlen (init);
strcpy ( ch, init );
}
String::String ( )//构造函数：创建一个空串
{
ch = new char[maxLen+1];
if ( !ch )
{
cout << "Allocation Error\n";
exit(1);
}
curLen = 0;
ch[0] = '\0';
}
String *String::operator ( ) ( int pos, int len )//从串中第pos个位置起连续提取len个字符//形成子串返回

{
String *temp = new String;
if ( pos < 0 || pos+len -1 >= maxLen|| len < 0 ) //返回空串
{

temp->curLen = 0;
temp->ch[0] = '\0';
}
else //提取子串
{
//动态分配
if ( pos+len -1 >= curLen )
len = curLen - pos;
temp->curLen = len; //子串长度
for ( int i=0, j=pos; i<len; i++, j++ )
temp->ch[i] = ch[j]; //传送串数组
temp->ch[len] = '\0'; //子串结束
}
return temp;
}
String &String::operator = ( const String &ob )//串赋值：从已有串ob复制
{
if ( &ob != this )
{
delete [ ] ch;
ch = new char [maxLen+1]; //重新分配
if ( ! ch )
{
cerr << "out of memory!\n ";
exit (1);
}
curLen = ob.curLen; //串复制
strcpy ( ch, ob.ch );
}
else
cout << "Attempted assignment of a String to itself!\n";
return *this;
}
char &String::operator [] ( int i ) //按串名提取串中第i个字符
{
if ( i < 0 && i >= curLen )
{
cout << "Out Of Boundary!\n ";
exit (1) ;
}
return ch[i];
}
String &String::operator += ( const String &ob )
{ //串连接
char * temp =ch; //暂存原串数组
curLen += ob.curLen; //串长度累加
ch = new char [maxLen+1];
if ( ! ch )
{
cerr << "Out Of Memory!\n ";
exit (1) ;
}
strcpy ( ch, temp ); //拷贝原串数组
strcat ( ch, ob.ch ); //连接ob串数组
delete [ ] temp;
return *this;
}
int String :: fastFind ( String pat ) const //带失效函数的KMP匹配算法
{
int posP = 0, posT = 0;
int lengthP = pat.curLen, lengthT = curLen;
int *f=new int[lengthP];
memset(f,-1,lengthP);
pat.fail (f);
while ( posP < lengthP && posT < lengthT )
{
if ( pat.ch[posP] == ch[posT] )
{
posP++;
posT++; //相等继续比较
}
else if ( posP == 0 )
{
posT++;
}//不相等
else
{
posP = f[posP-1]+1;
}
}
delete []f;
if ( posP < lengthP )
return -1;
else
return posT - lengthP;
}
void String::fail (int* &f)//计算失效函数
{
int lengthP = curLen;
f[0] = -1; //直接赋值
for ( int j=1; j<lengthP; j++ ) //依次求f [j]
{
int i = f[j-1];
if ( *(ch+j) != *(ch+i+1) && i >= 0 )
i = f [i]; //递推
if ( *(ch+j) == *(ch+i+1) )
f [j] = i+1;
else
f [j] = -1;
}
}
/**/
void main()
{
int end;
cout<<"hello!\n";
String s1("acabaabaabcacaabc");
String s2=("abaabcac");
end=s1.fastFind(s2);
cout<<end<<endl;
}

Ⅳ 急！kmp算法代码

LZ的get_next函数和Index_KMP函数的代码是复制粘贴的吧，那对应的是字符数组下标以1开始的代码，此外也有少量错误，修改后的正确代码如下。另外，LZ的代码中找不到next数组的定义，并且元素类型应该int才对头，这点需要在适当位置补充。

voidget_next(HString&T,int*next)
{
inti=0,j=-1;
next[0]=-1;/////关键
while(i<T.length-1)
{
if(j==-1||T.ch[i]==T.ch[j])
{
++i;
++j;
//////////////改进版KMP增加此判断/////////
if(T.ch[i]==T.ch[j])
next[i]==next[j];
else
////////////////////////////////////////////
next[i]==j;
}
else
j=next[j];
}
}

intIndex_KMP(HString&S,HString&T,intpos)
{
inti=pos,j=0;
get_next(T,next);
while(i<S.length&&j<T.length)
{
if(j==-1||S.ch[i]==T.ch[j])
{
++i;
++j;
}
else
j=next[j];
}
if(j>=T.length)
returni-T.length;//返回的匹配位置从下标0起算
else
return-1;//返回-1表示没有找到
}

Ⅳ kmp算法完整代码（C++）谢谢！

#include"stdio.h"
#include "conio.h"
#include "stdio.h"
#include "math.h"

int result;
char pat[]="kaka";
char str[]="iamkaka";
int next[7];

void getNext(char pat[], int next[])
{
int j = 0;
int k = -1;
next[0] = -1;
while (pat[j])
{
if ( k == -1 || pat[j] == pat[k])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k];
}
}
}
int KMP(char *str1, char*pat, int *next)
{
int i=0,j=0;
while(str[i])
{
if(pat[j]==0)
return i-j;
if(j==0 || str[i]==pat[j])
{
++i;
++j;
}else
j=next[j];
}
if(pat[j]==0)
return i-j;
return -1;
}

int main(int argc, char* argv[])
{
int i;

getNext(pat,next);
result=KMP(str,pat,next);
printf("%s\n",str);
for(i=0;i<result;i++) printf(" ");
printf("%s\n",pat);
printf("at %d\n",result);
getch();
return 0;
}

这个算法有点难理解的
Dev-C++ 编译测试通过：
结果：
iamkaka
kaka
at 3
祝你好运！
这种题目考试有必杀技的。我用颜色标注了的，但是这里不能用颜色来讲解NExt数组的变化。
有需要。给我留言！

Ⅵ KMP算法的C++代码

const vector<int> * kmp_next(string &m) // count the longest prefex string ;
{
static vector<int> next(m.size());
next[0]=0; // the initialization of the next[0];

int temp; // the key iterator......

for(int i=1;i<next.size();i++)
{
temp=next[i-1];

while(m[i]!=m[temp]&&temp>0)
{ temp=next[temp-1];
}

if(m[i]==m[temp])
next[i]=temp+1;
else next[i]=0;

}

return &next;

}

bool kmp_search(string text,string m,int &pos)
{
const vector<int> * next=kmp_next(m);

int tp=0;
int mp=0; // text pointer and match string pointer;

for(tp=0;tp<text.size();tp++)
{
while(text[tp]!=m[mp]&&mp)
mp=(*next)[mp-1];

if(text[tp]==m[mp])
mp++;

if(mp==m.size())
{ pos=tp-mp+1;
return true;
}
}

if(tp==text.size())
return false;
}

Ⅶ KMP算法的C语言程序

#include "iostream"
#include "stdlib.h"
#include "stdio.h"
#include "malloc.h"
#define MAXSTRLEN 100
#define OK 1
#define NULL 0
using namespace std;
typedef char SString[MAXSTRLEN+1];
SString T,S;
int next[MAXSTRLEN],c[MAXSTRLEN];
int i,j;
void get_next(SString &T,int next[MAXSTRLEN]){
i=1;next[1]=0;j=0;
while(i<T[0]){
if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}
else j=next[j];
}
}
int KMP(SString &S,SString &T){
i=1;j=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){++i;++j;}
else j=next[j];
}
if(j>T[0])return i-T[0];
else return 0;
}
void main(){
int k,p=1;
int i=1,j=1;
printf("输入主串：");
gets(&M[1]);
printf("输入模式串：");
gets(&N[1]);
while(M[i]!=NULL)
{
i++;
M[0]=i-1;
}
puts(&M[1]);

while(N[j]!=NULL)
{
j++;
N[0]=j-1;
}
puts(&N[1]);
if(M[0]>N[0])
{
printf("error!");
exit(0);
}
get_next(T,next);
for(i=1;i<=T[0];i++)printf("%d",next[i]);
printf("\n");
k=KMP(S,T);
printf("模式串从主串第%d个开始匹配！",k);
}

Ⅷ 求KMP算法例子

#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;

char str[100],t[100];
int next[100];

//计算最大滑动距离
void getnext()
{
int i,j,len;
len=strlen(str);
////////////////////////////////////////////////////////////////////////////经典的KMP算法
i=0, j=-1;
next[0] = -1;
while(i<len)
{
if(j==-1 || (j>=0 && str[i]==str[j]))
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
//*
//模式匹配，返回最小匹配的位置
int kmp()
{
int i = 0, j = 0;
int len = strlen(str),len2 = strlen(t);
while(i<len&&j<len2)
{
if(j==-1||str[i]==t[j])
{
++i,++j;
}
else j = next[j];
}
if(j>=len2)
return i-len2;
else return -1;
}
/////*/
int main()
{
while(scanf("%s %s",str,t)!=EOF)
{
getnext();
cout<<kmp()<<endl;
}
return 0;
}

Ⅸ KMP算法 看看代码哪里错了

搞定了请采纳最佳答案
#include<stdio.h>
#include<string.h>
voidgetnext(charT[],int*next)
{
	inti,j;
	i=0;
	j=-1;
	next[0]=-1;
	while(i<strlen(T))
	{
		if(j==-1||T[i]==T[j])
		{
			next[i+1]=j+1;
			i++;
			j++;
		}
		else
			j=next[j];
	}
}
intKMP(charS[],charT[])
{
	inti=0,j=0,next[100];
	getnext(T,next);
	while(i<strlen(S)&&j<strlen(T))
	{
		if(j==0||S[i]==T[j])
		{
			i++;
			j++;
		}
		else
		{
			j=next[j];
		}
	}
	if(j>=strlen(T))
		returni-strlen(T);
	else
		return-1;
}
voidmain()
{
	charS[100],T[100];
	printf("请输入主字符串S
");
	gets(S);
	printf("请输入子字符串T
");
	gets(T);
	printf("位置%d",KMP(S,T));
}

Ⅹ KMP模式匹配算法

这里有个相似的问题，也是我回答的，讲了原理
http://..com/question/329386416.html
如果你只要代码的话
一个简单的代码
#include <stdio.h>
#include <string.h>
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);

char s[10]="abcacbcba";
char t[4]="bca";
int next[4];
int pos=0;

int main()
{
int n;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
return 0;
}

int index_KMP(char *s,char *t,int pos)
{
int i=pos,j=1;
while (i<=(int)strlen(s)&&j<=(int)strlen(t))
{
if (j==0||s[i]==t[j-1])
{
i++;
j++;
}
else j=next[j];
}
if (j>(int)strlen(t))
return i-strlen(t)+1;
else
return 0;
}

void get_next(char *t,int *next)
{

int i=1,j=0;
next[0]=next[1]=0;
while (i<(int)strlen(t))
{
if (j==0||t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}

}