① 急！！急！！急！！数据结构（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;
}