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

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

}