Question

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

各位高手谁能帮我把KMP的算法在VC++6.0中运行，要求用C实现。要详细的代码。

Answer 1

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

Answer 2

代码如下:
#include <vector>
#include <string>
#include <iostream>
using namespace std;
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;
}

int main()
{
int pos=0;
kmp_search("abcacbc","ac",pos);
cout<<"position = "<<pos+1<<endl;
return 0;
}