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)

}

KMP.java

源代码为：

package algorithm.kmp

/**

* KMP算法的Java实现例子与测试、分析

* @author 崔卫兵

* @date 2009-3-25

*/

public class KMP {

/**

* 对子串加以预处理，从而找到匹配失败时子串回退的位置

* 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率

* 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组

* @param B，待查找子串的char数组

* @return

*/

public static int[] preProcess(char [] B) {

int size = B.length

int[] P = new int[size]

P[0]=0

int j=0

//每循环一次，就会找到一个回退位置

for(int i=1i<sizei++){

//当找到第一个匹配的字符时，即j>0时才会执行这个循环

//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）

//p1

while(j>0 &&B[j]!=B[i]){

j=P[j]

}

//p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化

if(B[j]==B[i]){

j++

}

//找到一个回退位置j，把其放入P[i]中

P[i]=j

}

return P

}

/**

* KMP实现

* @param parStr

* @param subStr

* @return

*/

public static void kmp(String parStr, String subStr) {

int subSize = subStr.length()

int parSize = parStr.length()

char[] B = subStr.toCharArray()

char[] A = parStr.toCharArray()

int[] P = preProcess(B)

int j=0

int k =0

for(int i=0i<parSizei++){

//当找到第一个匹配的字符时，即j>0时才会执行这个循环

//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）

//p1

while(j>0 &&B[j]!=A[i]){

//找到合适的回退位置

j=P[j-1]

}

//p2 找到一个匹配的字符

if(B[j]==A[i]){

j++

}

//输出匹配结果，并且让比较继续下去

if(j==subSize){

j=P[j-1]

k++

System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1)

}

}

System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr)

}

public static void main(String[] args) {

//回退位置数组为P[0, 0, 0, 0, 0, 0]

kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef")

//回退位置数组为P[0, 0, 1, 2, 3, 4]

kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit")

//回退位置数组为P[0, 0, 0]

kmp("测试汉字的匹配，崔卫兵。这个会匹配1次","崔卫兵")

//回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]

kmp("这个会匹配0次","it1it1it1")

}

}

#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

}*/

---