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];
}
}