① 急！！急！！急！！數據結構（C語言版）程序設計題： 使用KMP演算法實現一個模式匹配。
#include <cstring>
#include <iostream>
using namespace std;
//修正後的求next數組各值的函數代碼
void get_nextval(char const* ptrn, int plen, int* nextval)
{
int i = 0; //i是從0開始的
nextval[i] = -1;
int j = -1;
while( i < plen-1 )
{
if( j == -1 || ptrn[i] == ptrn[j] ) //循環的if部分
{
++i;
++j;
if( ptrn[i] != ptrn[j] ) //++i，++j之後，再次判斷ptrn[i]與ptrn[j]的關系
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else //循環的else部分
j = nextval[j];
}
}
void print_progress(char const* src, int src_index, char const* pstr, int pstr_index)
{
cout<<src_index<<"\t"<<src<<endl;
cout<<pstr_index<<"\t";
for( int i = 0; i < src_index-pstr_index; ++i )
cout<<" ";
cout<<pstr<<endl;
cout<<endl;
}
//int kmp_seach(char const*, int, char const*, int, int const*, int pos) KMP模式匹配函數
//輸入：src, slen主串
//輸入：patn, plen模式串
//輸入：nextval KMP演算法中的next函數值數組
int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)
{
int i = pos;
int j = 0;
while ( i < slen && j < plen )
{
if( j == -1 || src[i] == patn[j] )
{
++i;
++j;
}
else
{
j = nextval[j];
//當匹配失敗的時候直接用p[j_next]與s[i]比較，
//下面闡述怎麼求這個值，即匹配失效後下一次匹配的位置
}
}
if( j >= plen )
return i-plen;
else
return -1;
}
int main()
{
std::string src = "";
std::string prn = "abac";
int* nextval = new int[prn.size()];
//int* next = new int[prn.size()];
get_nextval(prn.data(), prn.size(), nextval);
//get_next(prn.data(), prn.size(), next);
for( int i = 0; i < prn.size(); ++i )
cout<<nextval[i]<<"\t";
cout<<endl;
cout<<"result sub str: "<<src.substr( kmp_search(src.data(), src.size(), prn.data(), prn.size(), nextval, 0) )<<endl;
system("pause");
delete[] nextval;
return 0;
}
望樓主採納！
② 數據結構中的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;}}
③ kmp演算法詳解
KMP模式匹配演算法
KMP演算法是一種改進的字元串匹配演算法,其關鍵是利用匹配失敗後的信息,盡量減少模式串與主串的匹配次數以達到快速匹配的目的明[4]。
求得模式的特徵向量之後，基於特徵分析的快速模式匹配演算法(KMP模式匹配演算法)與樸素匹配演算法類似，只是在每次匹配過程中發生某次失配時，不再單純地把模式後移一位，而是根據當前字元的特徵數來決定模式右移的位數[3]。
include "string. h"
#include<assert. h>
int KMPStrMatching(String T, String P, int. N, int startIndex)
{int lastIndex=T.strlen() -P.strlen();
if((1 astIndex- startIndex)<0)//若 startIndex過大,則無法匹配成功
return (-1);//指向P內部字元的游標
int i;//指向T內部字元的游標
int j=0;//指向P內部字元的游標
for(i= startIndex; i <T.strlen(); i++)
{while(P[j]!=T[i]&& j>0)
j=N[j-1];
if(P[j]==T[i])
j++;
if(j ==P.strlen())
return(1-j+1);//匹配成功,返回該T子串的開始位置
}
return (-1);
}
④ 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;
}