| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1046 人关注过本帖
标题:[原创]关于KMP算法
只看楼主 加入收藏
涛声依旧
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2005-3-5
收藏
 问题点数:0 回复次数:0 
[原创]关于KMP算法

/*字符串的顺序表示*/

#include<stdio.h> #include<stdlib.h>

#define MAXNUM 80 /* 串允许的最大字符个数。根据需要定义 */ struct SeqString { /* 顺序串的类型 */ int n; /*串的长度n<MAXNUM */ char c[MAXNUM]; }; typedef struct SeqString *PSeqString;

/*创建空顺序串*/ PSeqString createNullStr_seq( void ) { PSeqString pstr = (PSeqString)malloc(sizeof(struct SeqString)); /* 申请串空间 */ if (pstr == NULL) printf("Out of space!!\n"); else pstr->n = 0; return (pstr); }

/* 创建一个字符串,用C的串s初始化它 */ PSeqString createStr_seq( char *s ) { char *p, *q; PSeqString pstr = (PSeqString)malloc(sizeof(struct SeqString)); /* 申请串空间 */ if (pstr == NULL) printf("Out of space!!\n"); else { for ( p = q = pstr->c; *s != '\0' && p - q < MAXNUM; ) *p++ = *s++; pstr->n = p - q; }

return pstr; } /* 朴素子串匹配算法。求p所指的串在t所指的串中第一次出现时,*/ /* p所指串的第一个元素在t所指的串中的序号(即:下标+1) */ int index0( PSeqString t, PSeqString p ) { int i = 0, j = 0;/*初始化*/

while (i < p->n && j < t->n) /*反复比较*/ if (p->c[i] == t->c[j]) { /* 继续匹配下一个字符 */ i++; j++; } else { /* 主串、子串的i、j值回溯,重新开始下一次匹配 */ j -= i - 1; i = 0; }

if (i >= p->n) /* 匹配成功,返回p中第一个字符在t中的序号 */ return( j - p->n + 1); else return 0; /* 匹配失败 */ }

void makeNext1(PSeqString p, int *next) { int i = 0,k = -1; /* 初始化 */ next[0] = -1;

while (i < p->n-1) { /* 计算next[i+1] */ while (k >= 0 && p->c[i] != p->c[k])/* 找出p0~pi中最大的相同的前后缀长度k */ k = next[k]; i++; k++; next[i] = k; } } /*int index (s1,s2 ) 如果串s2是s1的子串,则可求串s2在串s1中第一次出现的位置. 参见模式匹配*/

/* 变量next是数组next的第一个元素next[0]的地址 */ void makeNext2(PSeqString p, int *next) { int i = 0,k = -1; /* 初始化 */ next[0] = -1;

while (i < p->n-1) { /* 计算next[i+1] */ while (k >= 0 && p->c[i] != p->c[k])/* 找出p0~pi中最大的相同的前后缀长度k */ k = next[k]; i++; k++; if (p->c[i] == p->c[k]) /* 填写next[i],同时考虑改善 */ next[i] = next[k]; else next[i] = k; } }

/*输出next数组的函数*/ void print_next(PSeqString p,int *next) { int i; for(i=0;i<p->n;i++) printf("%d ",next[i]); }

/* 无回溯的子串匹配算法,求p所指的串在t所指的串中第一次出现。*/ /* 有出现是返回p所指串的首元素在t所指串中的序号(从1开始),没有时返回0 */ int index(PSeqString t, PSeqString p) { int i = 0, j = 0; /* 初始化 */ int next[MAXNUM]; /* 内部索引数组 */

makeNext1(p, next); /* 在什么时候求next数组,可以考虑不同方式 , 调用makenext1实现改进前的next数组的求法, 调用makenext2实现改进前的next数组的求法*/ print_next(p,next); printf("\n");

while (i < p->n && j < t->n) /*反复比较*/ if ( i == -1 || p->c[i] == t->c[j] ) { /* 继续匹配下一字符 */ i++; j++; } else i = next[i]; /* j不变,i后退 */

if (i >= p->n) return( j - p->n + 1); /* 匹配成功,返回p中第一个字符在t中的序号 */ else return 0; /* 匹配失败 */ } /*输出顺序串的函数*/ void print_str(PSeqString P) { int i=0; for(i=0;i<P->n;i++) { printf("%c",P->c[i]); } }

void main() { int pos=0; /*存储模式匹配结果的变量*/ PSeqString S,T; /*S是模式串,T是目标串*/ S=createNullStr_seq(); T=createNullStr_seq(); S=createStr_seq("abca"); T=createStr_seq("aabcbabcaabcaababc"); printf("目标串为:"); print_str(T); printf("\n"); printf("模式串为:"); print_str(S); printf("\n"); pos=index0(T,S); printf("pos_BF=%d\n",pos); pos=index(T,S); printf("pos_KMP=%d\n",pos);

}

搜索更多相关主题的帖子: KMP 算法 PSeqString struct 顺序 
2005-04-26 12:13
快速回复:[原创]关于KMP算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.074038 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved