KMP优化算法求出的next数组错误
//预定义常量和类型//函数结果状态代码
#include <stdio.h>
#include<stdlib.h>
#include <time.h>
#include<windows.h>
#include<math.h>
//#include<unistd.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#define MAX_STR_LEN 255
typedef unsigned char String;
Status StrAssign(String T,char *chars)
{
//生成一个其值等于chars的串T
int i;
if(strlen(chars)>MAX_STR_LEN)
{
return ERROR;
}
else
{
T=strlen(chars);//0号单元存放串的长度
for(i=1;i<=T;i++)//从1号单元起复制串的内容
{
T=*(chars+i-1);
}
return OK;
}
}
void get_next( String T, int *next )
{
int j = 0;
int i = 1;
next = 0;
while( i < T )
{
if( 0 == j || T == T )
{
i++;
j++;
if( T != T )
{
next = j;
}
else
{
next = next;
}
}
else
{
j = next;
}
}
for(i=1;i<=T;i++)
{
printf("%d ",next);
}
printf("\n");
}
// 杩斿洖瀛愪覆T鍦ㄤ富涓睸绗琾os涓瓧绗︿箣鍚庣殑浣嶇疆
// 鑻ヤ笉瀛樺湪锛屽垯杩斿洖0
int Index_KMP( String S, String T, int pos )
{
int i = pos;
int j = 1;
int next;
get_next( T, next );
while( i <= S && j <= T )
{
if( 0 == j || S == T )
{
i++;
j++;
}
else
{
j = next;
}
}
if( j > T )
{
return i - T;
}
else
{
return 0;
}
}
main()
{
char *chars1="ababaaaba"; //这里赋值给T
char *chars2="fababcabdabababaaabacabeabababe";
String T,S;
int next;
StrAssign(T,chars1);
StrAssign(S,chars2);
get_next(T, next );
return 0;
}
模式串T="ababaaaba"
优化算法得出的next数组=0 1 0 1 0 4 2 1 0
正确的next数组应该 是=0 1 1 2 3 4 2 2 3
请问是为什么，是算法错了吗
谁帮我看下啊 谁帮下我啊 没有问题了，两个数组都可以得到一样的匹配结果，昨天支行时老出错，今天就可以了，谢谢大家，问题解决了
页:
[1]