|
1鱼币
- //预定义常量和类型
- //函数结果状态代码
- #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[MAX_STR_LEN+1];
- Status StrAssign(String T,char *chars)
- {
- //生成一个其值等于chars的串T
- int i;
- if(strlen(chars)>MAX_STR_LEN)
- {
- return ERROR;
- }
- else
- {
- T[0]=strlen(chars);//0号单元存放串的长度
- for(i=1;i<=T[0];i++)//从1号单元起复制串的内容
- {
- T[i]=*(chars+i-1);
- }
- return OK;
- }
- }
- void get_next( String T, int *next )
- {
- int j = 0;
- int i = 1;
- next[1] = 0;
- while( i < T[0] )
- {
- if( 0 == j || T[i] == T[j] )
- {
- i++;
- j++;
- if( T[i] != T[j] )
- {
- next[i] = j;
- }
- else
- {
- next[i] = next[j];
- }
- }
- else
- {
- j = next[j];
- }
- }
- for(i=1;i<=T[0];i++)
- {
- printf("%d ",next[i]);
- }
- printf("\n");
- }
- // 杩斿洖瀛愪覆T鍦ㄤ富涓睸绗琾os涓瓧绗︿箣鍚庣殑浣嶇疆
- // 鑻ヤ笉瀛樺湪锛屽垯杩斿洖0
- int Index_KMP( String S, String T, int pos )
- {
- int i = pos;
- int j = 1;
- int next[255];
- get_next( T, next );
- while( i <= S[0] && j <= T[0] )
- {
- if( 0 == j || S[i] == T[j] )
- {
- i++;
- j++;
- }
- else
- {
- j = next[j];
- }
- }
- if( j > T[0] )
- {
- return i - T[0];
- }
- else
- {
- return 0;
- }
- }
- main()
- {
- char *chars1="ababaaaba"; //这里赋值给T
- char *chars2="fababcabdabababaaabacabeabababe";
- String T,S;
- int next[255];
- 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
请问是为什么,是算法错了吗
|
|