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=1next[1]=0j=0

while(i<T[0]){

if(j==0||T[i]==T[j]){++i++jnext[i]=j}

else j=next[j]

}

}

int KMP(SString &S,SString &T){

i=1j=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=1i<=T[0]i++)printf("%d",next[i])

printf("配戚源\n")

k=KMP(S,T)

printf("模式串仔态从主串第%d个开始匹配！",k)

}

#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 = -1i <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 = 0i <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}}

#include <iostream>

#include <windows.h> //for PTSTR

#include <strsafe.h> //for StringCchLength() StringCchCopy()

class StringKMP{

public:

StringKMP():m_str(NULL), m_nextval(NULL), m_size(0){}

~StringKMP(){

if(m_str != NULL){

free(m_str)

m_str = NULL

}

if(m_nextval != NULL){

free(m_nextval)

m_nextval = NULL

}

std::cout <<"..."

}

void setString(PCTSTR psz) //设置用于匹配的字符串

int indexKMP(PCTSTR pDest, int pos) //匹配失败，返回-1

private:

PTSTRm_str

intm_size

int *m_nextval

void get_nextval() //枯裂拿求模式串的next修正值并存入数组m_nextval

}

--StringKMP.cpp--

// StringKMP.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include "StringKMP.h"

void StringKMP::setString(PCTSTR psz){//设置用于匹配的字符串没搭

int size

StringCchLength(psz, STRSAFE_MAX_CCH, (size_t *)&size)

m_size = size

if(m_str != NULL){

free(m_str)

m_str = NULL

}

if(m_nextval != NULL){

free(m_nextval)

m_nextval = NULL

}

m_str = (PTSTR)malloc(( size + 1 ) * sizeof(TCHAR))

StringCchCopy(m_str, size + 1, psz)

m_nextval = (int *)malloc( size * sizeof(int))

memset(m_nextval, 0, size * sizeof(int))

get_nextval()

}

int StringKMP::indexKMP(PCTSTR pDest, int pos){//从pos位置进行查找

//匹配失败，返回-1

//利用模式串的m_nextval求模式源升串在pDest中第pos个字符之后的位置的KMP算法。

//其中，0 <= pos <len(pDest)

int i = pos

int j = 0

int size

StringCchLength(pDest, STRSAFE_MAX_CCH, (size_t *)&size)

while(i <size &&j <m_size){

if(j == -1 || pDest[i] == m_str[j]){

++i

++j

}

else{

j = m_nextval[j]

}

}

if(j == m_size){//匹配成功

return i - m_size - pos

}

else//匹配失败，返回-1

return -1

}

void StringKMP::get_nextval(){

//求模式串的next函数修正值并存入数组m_nextval

int i = 0, j = -1

m_nextval[0] = -1

while(i <m_size - 1){

if(j == -1 || m_str[i] == m_str[j]){

++i

++j

if(m_str[i] != m_str[j])

m_nextval[i] = j

else

m_nextval[i] = m_nextval[j]

}

else{

j = m_nextval[j]

}

}

}

下面语句可以用来测试

/*int _tmain(int argc, _TCHAR* argv[])

{

StringKMP kmp

kmp.setString(TEXT("un"))

std::cout <<kmp.indexKMP(TEXT("HungryAnt"), 0) <<std::endl

std::cout <<kmp.indexKMP(TEXT("HungryAnt"), 1) <<std::endl

std::cout <<kmp.indexKMP(TEXT("HungryAn"), 2) <<std::endl

kmp.setString(TEXT("Ant"))

std::cout <<kmp.indexKMP(TEXT("HungryAnt"), 0) <<std::endl

std::cout <<kmp.indexKMP(TEXT("HungryAnt"), 1) <<std::endl

std::cout <<kmp.indexKMP(TEXT("HungryAn"), 2) <<std::endl

return 0

}*/

---