Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3255005
  • 博文数量: 282
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2089
  • 用 户 组: 普通用户
  • 注册时间: 2019-10-28 13:40
文章分类

全部博文(282)

文章存档

2022年(55)

2021年(155)

2020年(50)

2019年(22)

我的朋友

分类: 信息化

2020-03-23 16:50:58

#include
#include
void sstring(chara,charb)//将一个字符串整体后移一个单位方便后续计算
{
int len,i;
a[0]=strlen(b);
for(i=1;i<=a[0];i++)
a[i]=b[i-1];
return;
}
void get_next(char* T,int *next) //next函数求法运用了递推的思想,即从广义的某个字符t[i]开始推出普遍规律 其中又再次运用了kmp思想
{
int i=1,j=0;
next[1]=0;
while(i
if(j==0||T[i]==T[j])//j=0意味着无相同前后缀,模式串从首位开始重新与主串匹配
{
++i;
++j;
next[i]=j; //这三步可以直接写成 next[++i]=++j;
}
else
j=next[j];//仍然不匹配 模式串右滑
}


/* void get_next(char* T,int next)
{
int i=1,j=0;
next[1]=0;
while(i
if(T[i]= =T[j])
{
++i;
++j;
next[i]=j;
}
else if(j==0) //实际上是三种情况 但第二种if完全可以合并到第一种if中
{
j=1;
i++;
next[i]=1;
}
else
j=next[j];//仍然不匹配 模式串右滑
}/

英镑符号

int KMP(charS,charT,int pos,int*next) //next函数是基于kmp算法实现的 只要清楚next函数的算法,kmp算法就可以搞明白
{
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()
{
char s1[1000],s2[1000],t[1000],p[1000];
int i,next[1000];
printf(“请输入主串\n”);
gets(s1);
printf(“请输入模式串\n”);
gets(s2);
sstring(t,s1);
sstring(p,s2);
get_next(p,next);
i=KMP(t,p,1,next);
if(i)
printf(“主串和子串在第%d个字符处首次匹配\n”,i);
else
printf(“主串和子串匹配不成功\n”);
}

阅读(996) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~