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")

}

}

---