本文主要是介绍数据结构串的实现以及KMP改进算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
</pre><pre name="code" class="cpp">#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 40 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
/* 输出字符串T */
void StrPrint(String T)
{int i;for(i=1;i<=T[0];i++)printf("%c",T[i]);printf("\n");
}
/* 生成一个其值等于chars的串T */
Status StrAssign(String T,char *chars)
{int i;if(strlen(chars)>MAXSIZE)return ERROR;else{T[0]=strlen(chars);//T[0]存储串的长度for(i=1;i<=T[0];i++)T[i]=*(chars+i-1);return OK;}
}
/* 返回串的元素个数 */
int StrLength(String S)
{return S[0];
}/* 初始条件: 串S和T存在 */
/* 操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S < T,则返回值< 0 */
int StrCompare(String S,String T)
{int i;for(i=1;i <=S[0]&&i<=T[0];++i)if(S[i]!=T[i])return S[i]-T[i];return S[0]-T[0];
}/* 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE */
Status Concat(String T,String S1,String S2)
{int i;if(S1[0]+S2[0]<=MAXSIZE){ /* 未截断 */for(i=1;i<=S1[0];i++)T[i]=S1[i];for(i=1;i<=S2[0];i++)T[S1[0]+i]=S2[i];T[0]=S1[0]+S2[0];return TRUE;}else{ /* 截断S2 */for(i=1;i<=S1[0];i++)T[i]=S1[i];for(i=1;i<=MAXSIZE-S1[0];i++)T[S1[0]+i]=S2[i];T[0]=MAXSIZE;return FALSE;}
}/* 用Sub返回串S的第pos个字符起长度为len的子串。 */
Status SubString(String Sub,String S,int pos,int len)
{int i;if(pos < 1||pos>S[0]||len < 0||len>S[0]-pos+1)return ERROR;for(i=1;i<=len;i++)Sub[i]=S[pos+i-1];Sub[0]=len;return OK;
}
void get_next(String T,int *next)
{int i,j;i=1;j=0;next[1]=0;while(i<T[0]){if(j==0||T[i]==T[j]){i++;j++;next[i]=j;}else{j=next[j];}}
}
void get_nextval(String T,int *nextval)
{int i,j;i=1;j=0;nextval[1]=0;while(i<T[0]){if(j==0||T[i]==T[j]){i++;j++;if(j==0||T[i]!=T[j])nextval[i]=j;elsenextval[i]=nextval[j];}else{j=nextval[j];}}
}
int Index_KMP(String S,String T,int pos)
{int i=pos;//从pos位置开始int j=1;int next[255];//定义一组next数组//get_next(T,next);get_nextval(T,next);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];}elsereturn 0;
}
int main()
{String S,T;char *s="acdefgab";char *t="ab";StrAssign(S,s);StrAssign(T,t);int a= Index_KMP(S,T,1);printf("%d",a);return 0;
}
这篇关于数据结构串的实现以及KMP改进算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
