串的模式匹配
发布网友
发布时间：2022-04-25 03:17
共2个回答
热心网友
时间：2023-10-22 21:26
# include <stdio.h>
# include <stdlib.h>
# define OK 1
# define ERROR 0
typedef int Status;
//串的定长顺序存储结构
# define MAX_STR_LEN 40
typedef char SString[MAX_STR_LEN + 1];//0号单元存放串的长度
Status StrAssign(SString T,char * chars)//生成一个其值等于chars的串T
{
int i;
if (strlen(chars) > MAX_STR_LEN)
{
return ERROR;
}
else
{
T[0] = strlen(chars);
for (i=1; i<=T[0]; ++i)
{
T[i] = * (chars + i - 1);
}
return OK;
}
}
//返回串S的元素的个数
int StrLength(SString S)
{
return S[0];
}
//用Sub返回串S的自第pos个字符起长度为len的子串
Status SubString(SString Sub,SString 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;
}
//输出字符串T
void StrPrint(SString T)
{
int i;
for (i=1; i<=T[0]; ++i)
{
printf("%c ",T[i]);
}
printf("\n");
}
//求模式串T的next函数值并存入数组next
void get_next(SString T,int next[])
{
int 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];
}
}
}
//求模式串T的next函数修正值并存入数组nextval
void get_nextval(SString T,int nextval[])
{
int i = 1,j = 0;
nextval[1] = 0;
while (i < T[0])
{
if (j==0 || T[i]==T[j])
{
++i;
++j;
if (T[i] != T[j])
{
nextval[i] = j;
}
else
{
nextval[i] = nextval[j];
}
}
else
{
j = nextval[j];
}
}
}
//利用模式串T的next函数求T在主串S中第pos字符之后的位置的KMP算法
//1=<pos=<StrLength(S)
int Index_KMP(SString S,SString T,int pos,int next[])
{
int i = pos,j = 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;
}
}
int main(void)
{
int i,* p;
SString s1,s2;
StrAssign(s1,"aaabaaaab");
printf("主串为：");
StrPrint(s1);
StrAssign(s2,"aaaab");
printf("子串为：");
StrPrint(s2);
p = (int *)malloc((StrLength(s2) + 1) * sizeof(int));
get_next(s2,p);
printf("子串的next的数组为：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
i = Index_KMP(s1,s2,1,p);
if (i)
{
printf("主串和子串在第%d个字符处首次匹配\n",i);
}
else
{
printf("主串和子串匹配不成功\n");
}
get_nextval(s2,p);
printf("子串的nextval数组为：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
printf("主串和子串在第%d个字符处首次匹配\n",Index_KMP(s1,s2,1,p));
printf("求串s1的从第5个字符起长度为5的子串s2:\n");
SubString(s2,s1,5,5);
printf("串s2为:");
StrPrint(s2);
return 0;
}
/*
在vc++6.0中的输出结果：
------------------------
主串为：a a a b a a a a b
子串为：a a a a b
子串的next的数组为：0 1 2 3 4
主串和子串在第5个字符处首次匹配
子串的nextval数组为：0 0 0 0 4
主串和子串在第5个字符处首次匹配
求串s1的从第5个字符起长度为5的子串s2:
串s2为:a a a a b
Press any key to continue
------------------------------
*/
请采纳答案，支持我一下。
热心网友
时间：2023-10-22 21:26
