소스코드 좀 봐주세요
글쓴이: 이상훈 / 작성시간: 월, 2003/08/04 - 4:50오전
Aho-Corasick Algorithm 구현할려구 만든 소스인데 텍스트에서 2~8자의 문자열을 입력받고, 그것을 이용해서 트리를 생성하는 소스입니다.
트리를 배열로 구현할려고 하는데, 뭐가 문제인지 모르겠네요...ㅠㅠ
depth가 계속 증가만하고, 문자열도 제대로 입력 받지 못하는 것 같고...ㅠㅠ
고수님들 도와주세요..ㅠ0ㅠ
/*table.txt state table */
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<fstream.h>
#include<iostream.h>
struct StateTable{
char forNext;
int NextState;
int failState;
bool isOutput;
};
struct outputTable{
int state;
char output[8];
};
struct depthTable{
int State[1000];
};
int r_depthTable[8000] ={0};
typedef struct outputTable outputTable;
typedef struct StateTable StateTable;
typedef struct depthTable depthTable;
StateTable wStateTable[8000][30];
outputTable woutputTable[1000];
depthTable wdepthTable[10];
int finalState = 0;
int finalsubState = 0;
int finaloutput = 0;
int Failure(int state, char tmp_char);
void constructTable(char cur_input[8]);
void constructOutput(int tState, char *tempinput);
void main()
{
FILE *input,*result;
if((input = fopen("text1.txt","rb"))== NULL) /*text1.txt : input string*/
{
printf("can't open file for reading");
exit(1);
}
if((result = fopen("table.txt","wb")) ==NULL)
{
printf("can't open file for writing");
exit(1);
}
char cur_input[8];
int tState = 0;
int k;
srand( (unsigned)time( NULL ) );
k = (rand()%8)+1;
while(fread(cur_input, k, 1,input) == 1)
{
printf("%c\n",cur_input);
constructTable(cur_input);
k = (rand()%8)+1;
free(cur_input);
}
int t_depth = 0;
for(int a=1;a<8000;a++)
{
t_depth = r_depthTable[a];
printf("%d",t_depth);
int u = 0;
while(wdepthTable[t_depth].State[u] != 0)
u++;
wdepthTable[t_depth].State[u] = a;
}
for(int i=0;i<8000;i++)
for(int j=0;j<30;j++)
{
if(wStateTable[i][j].forNext == '\n')
{
wStateTable[i][j].failState = 0;
continue;
}
wStateTable[i][j].failState = Failure(i, wStateTable[i][j].forNext);
}
fwrite(wStateTable,sizeof(StateTable),1,result);
fclose(input);
fclose(result);
}
void constructTable(char tempinput[])
{
r_depthTable[1] = 1;
r_depthTable[0] = 0;
char curinput[8];
int kth = 0;
*curinput = *tempinput;
int _tState = 0;
int tempState = 0;
wStateTable[0][0].NextState = 1;
for(int j = 0 ; j<30 ; j++)
{
if ((wStateTable[_tState][j].forNext == '\n') || (wStateTable[_tState][j].forNext == NULL))
break;
if(wStateTable[_tState][j].forNext == ((char) curinput[kth]))
{
_tState = wStateTable[_tState][j].NextState;
j = 0;
kth++;
if( (curinput[kth]) == '\n')
{
constructOutput(_tState, tempinput);
exit(1);
}
}
}
while((curinput[kth]) != '\n')
{
for(int z=0 ; z<30 ; z++)
if(wStateTable[_tState][z].forNext == '\n')
break;
r_depthTable[finalState + 1] = r_depthTable[_tState]+1;
wStateTable[_tState][z].forNext =curinput[kth];
wStateTable[_tState][z].isOutput = 0;
wStateTable[_tState][z].failState = 0;
wStateTable[_tState][z].NextState = (finalState++);
_tState = finalState;
kth++;
}
wStateTable[_tState][0].isOutput = 1;
constructOutput(_tState, tempinput);
}
void constructOutput(int tState, char tempinput[])
{
woutputTable[finaloutput].state = tState;
*woutputTable[finaloutput].output = *tempinput;
finaloutput++;
}
int Failure(int state, char tmp_char)
{
int depth = r_depthTable[state];
if(depth == 0 || depth == 1)
return 0;
int tState = 0;
int i = 0;
while((tState = wdepthTable[depth - 1].State[i]) !=0)
{
for(int j=0; j<30;j++)
{
if(wStateTable[tState][j].forNext == tmp_char)
return tState;
}
i++;
}
return 0;
}Forums:


댓글 달기