KMP模式匹配 一(串)
时间: 1ms 内存:128M
描述:
求子串的next值,用next数组存放,全部输出
输入:
输入一个字符串
输出:
输出所有next值
示例输入:
abaabcac
示例输出:
0 1 1 2 2 3 1 2
提示:
参考答案(内存最优[752]):
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
typedef struct
{
char data[20];
int length;
}sqstring;
void getnext(sqstring *t,int next[])
{
int j,k;
j=0;
k=-1;
next[0]=-1;
while(j<t->length-1){
if(k==-1||(t->data[j]==t->data[k])){
j++;
k++;
next[j]=k;
}
else
k=next[k];
}
}
int main()
{
int i,a[20];
sqstring *t;
t=(sqstring *)malloc(sizeof(sqstring));
char h[20];
gets(h);
for(i=0;h[i]!='\0';i++)
t->data[i]=h[i];
t->length=i;
getnext(t, a);
for(i=0;i<t->length-1;i++)
printf("%d ",a[i]+1);
printf("%d\n",a[t->length-1]+1);
return 0;
}
参考答案(时间最优[0]):
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
typedef struct
{
char data[20];
int length;
}sqstring;
void getnext(sqstring *t,int next[])
{
int j,k;
j=0;
k=-1;
next[0]=-1;
while(j<t->length-1){
if(k==-1||(t->data[j]==t->data[k])){
j++;
k++;
next[j]=k;
}
else
k=next[k];
}
}
int main()
{
int i,a[20];
sqstring *t;
t=(sqstring *)malloc(sizeof(sqstring));
char h[20];
gets(h);
for(i=0;h[i]!='\0';i++)
t->data[i]=h[i];
t->length=i;
getnext(t, a);
for(i=0;i<t->length-1;i++)
printf("%d ",a[i]+1);
printf("%d\n",a[t->length-1]+1);
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。