#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 26
typedef struct DocNode{
char ch;
int times[3001];
struct DocNode *next[300];
struct DocNode *nextword[3001];
}DocNode, *DNode;
int DocInit (DNode DRoot, FILE *fp) {
char a[100], b;
int i, j, k, t, nu=0;
DNode p, q;
while (1) {
if (fgetc(fp) == EOF) break;
else nu++;
while (fgetc(fp)!=10) continue;
while (1) {
for (t=0;t<100;t++) a[t]='\0';
for (i=0,b = fgetc(fp);b!=32&&b!=10&&b!=EOF;b=fgetc(fp)) a[i++]=b;
q=p=DRoot;j=0;
while (j<i) {
for (k=0;k<300;k++) {
if (p->next[k]==NULL) {
p->next[k] = (DNode)malloc(sizeof(DocNode));
p->next[k]->ch = a[j];
for (t=0;t<3001;t++) {
p->next[k]->times[t]=0;
p->next[k]->nextword[t]=NULL;
}
for (t=0;t<3001;t++) p->next[k]->next[t]=NULL;
if (j==i-1) {
p->next[k]->times[nu]=1;
q->nextword[nu]=p->next[k];
q=p->next[k];
}
p=p->next[k];break;
}
else if (p->next[k]->ch==a[j] && j!=i-1) {p=p->next[k];break;}
else if (p->next[k]->ch==a[j] && j==i-1 && p->next[k]->times[nu]==0) {
p->next[k]->times[nu]++;
q->nextword[nu]=p->next[k];
q=p->next[k];
q->nextword[nu]=NULL;
break;
}
else continue;
}
j++;
}
if (b==10||b==EOF) break;
}
}
return nu;
}
int Sin_Traverse(DNode p, char *a, int t, int i, int nu, int tag) {
int k;
if (tag==1) return tag;
if (t==i) return tag;
for (k=0;p->next[k]!=NULL;k++) {
if (p->next[k]->ch==a[t]) {
if (t==i-1 && p->next[k]->times[nu]==1) return tag=1;
else if (t==i-1 && p->next[k]->times[nu]==0) continue;
else tag=Sin_Traverse(p->next[k],a,t+1,i,nu,tag);
}
}
return tag;
}
void WordInDocument (DNode DRoot,FILE *fp, FILE *fq,int nu) {
int k, ca=1, tag, i;
char a[100], b;
while (1) {
for(k=0;k<100;k++) a[k]='\0';
i=0;
b=fgetc(fp);
if (b==EOF) break;
while (b!=10 && b!=EOF) {a[i++]=b;b=fgetc(fp);}
fprintf(fq,"CASE %d：\n",ca++);
for (k=1;k<nu+1;k++) {
tag=0;
tag=Sin_Traverse(DRoot,a,0,i,k,0);
if (tag==1) fprintf(fq,"%d ",k);
}
fprintf(fq,"\n");
}
}
int MultiTraverse (DNode root, DNode p, char **a, int w, int t, int tag, DNode q, int nu) {
int i =0,k;
if (tag==1) return tag;
while (a[w][i]!='\0') i++;
for (k=0;p->next[k]!='\0';k++) {
if (p->next[k]->ch==a[w][t]) {
if (t==i-1) {
if(p->next[k]->times[nu]==0) continue;
else if (w==0) tag=MultiTraverse(root,root,a,w+1,0,tag,p->next[k],nu);
else if (q->nextword[nu]!=p->next[k]) continue;
else if (a[w+1][0]!='\0') tag=MultiTraverse(root,root,a,w+1,0,tag,p->next[k],nu);
else if (a[w+1][0]=='\0') return tag=1;
else continue;
}
else tag=MultiTraverse(root,p->next[k],a,w,t+1,tag,q,nu);
}
}
return tag;
}
void TwoWordInDocument (DNode DRoot, FILE *fp, FILE *fq, int nu) {
int w, i, k, j, ca=1, tag;
char a[2][20], b;
while (1) {
for (k=0;k<2;k++)
for (j=0;j<20;j++)
a[k][j]='\0';
w=0;
b=fgetc(fp);
if (b==EOF) break;
while (1) {
for (i=0;b!=32 && b!= 10 && b!=EOF;b=fgetc(fp)) a[w][i++]=b;
if (b==32) w++;
if (b==10 || b==EOF) break;
}
fprintf(fq,"CASE %d：\n",ca++);
for (k=1;k<nu+1;k++) {
tag=0;
tag=MultiTraverse(DRoot,DRoot,a,0,0,0,NULL,k);
if (tag==1) fprintf(fq,"%d ",k);
}
if (b==EOF) break;
}
}
void MultiWordInDocument (DNode DRoot, FILE *fp, FILE *fq, int nu) {
int w, i, k, j, ca=1, tag;
char a[6][20], b;
while (1) {
for (k=0;k<6;k++)
for (j=0;j<20;j++)
a[k][j]='\0';
w=0;
b=fgetc(fp);
while(b!=10) {b=fgetc(fp);continue;}
if (b==EOF) break;
while (1) {
for (i=0;b!=32 && b!= 10 && b!=EOF;b=fgetc(fp)) a[w][i++]=b;
if (b==32) w++;
if (b==10 || b==EOF) break;
}
fprintf(fq,"CASE %d：\n",ca++);
for (k=1;k<nu+1;k++) {
tag=0;
tag=MultiTraverse(DRoot,DRoot,a,0,0,0,NULL,k);
if (tag==1) fprintf(fq,"%d ",k);
}
if (b==EOF) break;
}
}
int main(void) {
int DocNum, i;
FILE *fp, *fq;
DNode DRoot;
DRoot=(DNode)malloc(sizeof(DocNode));
DRoot->ch='\0';
for (i=0;i<3001;i++) {
DRoot->times[i]=0;
DRoot->nextword[i]=NULL;
}
for (i=0;i<300;i++) DRoot->next[i]=NULL;
fp = fopen("./Document/Document.txt","r");
printf("根据Documnet目录下的document.txt文件建立字典序...\n");
DocNum=DocInit(DRoot, fp);
fclose(fp);
fp = fopen("./WordInDocument/WordInDocument.txt","r");
fq = fopen("./WordInDocument/WordInDocument_Result.txt","a+");
printf("根据WordInDocument目录下WordInDocument.txt找出单词所在的Document（结果参见同目录下的WordInDocument_Result.txt文件）...\n");
WordInDocument(DRoot,fp,fq,DocNum);
fclose(fp);fclose(fq);
fp = fopen("./WordInDocument/SmallWordInDocument.txt","r");
fq = fopen("./WordInDocument/SmallWordInDocument_Result.txt","a+");
printf("根据WordInDocument目录下SmallWordInDocument.txt找出单词所在的Document（结果参见同目录下的SmallWordInDocument_Result.txt文件）...\n");
WordInDocument(DRoot,fp,fq,DocNum);
fclose(fp);fclose(fq);
fp = fopen("./TwoWordInDocument/TwoWordInDocument.txt","r");
fq = fopen("./TwoWordInDocument/TwoWordInDocument_Result.txt","a+");
printf("根据TwoWordInDocument目录下TwoWordInDocument.txt找出单词所在的Document（结果参见同目录下的TwoWordInDocument_Result.txt文件）...\n");
TwoWordInDocument (DRoot, fp, fq, DocNum);
fclose(fp);fclose(fq);
fp = fopen("./TwoWordInDocument/SmallTwoWordInDocument.txt","r");
fq = fopen("./TwoWordInDocument/SmallTwoWordInDocument_Result.txt","a+");
printf("根据TwoWordInDocument目录下SmallTwoWordInDocument.txt找出单词所在的Document（结果参见同目录下的SmallTwoWordInDocument_Result.txt文件）...\n");
TwoWordInDocument (DRoot, fp, fq, DocNum);
fclose(fp);fclose(fq);
fp = fopen("./MultiWordInDocument/MultiWordInDocument.txt","r");
fq = fopen("./MultiWordInDocument/MultiWordInDocument_Result.txt","a+");
printf("根据MultiWordInDocument目录下MultiWordInDocument.txt找出单词所在的Document（结果参见同目录下的MultiWordInDocument_Result.txt文件）...\n");
MultiWordInDocument (DRoot, fp, fq, DocNum);
fclose(fp);fclose(fq);
fp = fopen("./MultiWordInDocument/SmallMultiWordInDocument.txt","r");
fq = fopen("./vWordInDocument/SmallMultiWordInDocument_Result.txt","a+");
printf("根据MultiWordInDocument目录下SmallMultiWordInDocument.txt找出单词所在的Document（结果参见同目录下的SmallMultiWordInDocument_Result.txt文件）...\n");
MultiWordInDocument (DRoot, fp, fq, DocNum);
fclose(fp);fclose(fq);
free(DRoot);
return 0;
}