应用题：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;
}

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