应用题:KMP算法

应用题:KMP算法

时间: 1ms        内存:128M

描述:

已知KMP串匹配算法中子串为''babababaa'', 求数组next[ ]请完善下面的next数组,并将下面的9行提交。

注意:应用题不用编程,也不进行现场评判,提交代码后自动显示“AC”。建议你确保答案正确后再提交。

next[0]=-1;
next[1]=......;
next[2]=......;
next[3]=......;
next[4]=......;
next[5]=......;
next[6]=......;
next[7]=......;
next[8]=......;

输入:

输出:

示例输入:

示例输出:

提示:

参考答案(内存最优[0]):

#include<stdio.h>
#include<string.h>
int next[100];
void f(char  arr[])
{
    int i,j=0,k=-1;
    next[0]=-1;
    while(j<strlen(arr)-1)
    {
        if(k==-1||arr[j]==arr[k])
            next[++j]=++k;
        else k=next[k];
    }
}
int main()
{
    char arr[100];
    gets(arr);
    f(arr);
    int i;
    for(i=0;i<strlen(arr);i++)
        printf("next[%d]=%d\n",i,next[i]);
}

参考答案(时间最优[0]):


#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main()
{
    int next[80];
    int num = 9;
    int i;
next[0]=-1;
next[1]=0;
next[2]=0;
next[3]=1;
next[4]=2;
next[5]=3;
next[6]=4;
next[7]=5;
next[8]=6;
    for(i=0; i<num; i++)
        printf("%d ",next[i]);
    printf("\n");
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注