I am really getting crazy over this question. I know I am supposed to use trie, and that's what I did. However, I am still getting WA. Here's my code
- Code: Select all
#include <stdio.h>
#include <string.h>
struct nodeT{
int end;
struct nodeT *next[26];
};
char delim[] = "`~1!2@3#4$5%6^7&8*9(0)-_=+[{]}\\|;:'\",<.>/? \n";
int i,j,k,np,len,total,flag,cnt;
struct nodeT root;
struct nodeT nodes[30000];
int len1[6000];
char str[100];
char table[6000][6];
char hash[20];
char salt[3];
char key[10];
char path[10];
char *crypt(char *pw, char *salt);
void tolower(char *c){
int ii;
for (ii=0;c[ii]!=0;ii++){
c[ii] |= 0x20;
}
return;
}
void addWord(struct nodeT *p, char *word){
int ii, id,len = strlen(word);
struct nodeT *v;
for (ii=0;ii<len;ii++){
id = word[ii]-'a';
if (p->next[id]==NULL){
memset(&nodes[np],0x0,sizeof (struct nodeT));
p->next[id] = &nodes[np];
np++;
}
p = p->next[id];
if (ii == len - 1)
p->end = 1;
}
return;
}
void printtrie(struct nodeT *p, int depth){
int ii,iszero;
path[depth] = 0;
if (p->end == 1){
len1[cnt] = strlen(path);
strcpy(table[cnt],path);
cnt++;
}
for (ii=0,iszero=1;ii<26;ii++){
if (p->next[ii] != 0){
path[depth] = ii+'a';
printtrie(p->next[ii],depth+1);
iszero = 0;
}
}
if (iszero != 0 && p->end == 0){
len1[cnt] = strlen(path);
strcpy(table[cnt],path);
cnt++;
}
return;
}
int main(){
char *pch;
memset(&root,0x0,sizeof(struct nodeT));
np = 0; cnt = 0;
gets(hash);
salt[0] = hash[0]; salt[1] = hash[1];
while (gets(str)!=NULL){
pch = strtok(str,delim);
while (pch!=NULL){
len = strlen(pch);
if (len < 6 && len > 1){
tolower(pch);
addWord(&root,pch);
}
pch = strtok(0,delim);
}
}
printtrie(&root,0);
flag = 0;
for (i=0;i<(cnt-1);i++){
for (j=i+1;j<cnt;j++){
total = len1[i] + len1[j] + 1;
if (total >= 5 && total <= 8){
for (k=0;k<10;k+=2){
if (k==6)
continue;
sprintf(key,"%s%d%s",table[i],k,table[j]);
if (strcmp(crypt(key,salt),hash)==0){
flag = 1;
break;
}
}
}
if (flag == 1)
break;
}
if (flag == 1)
break;
}
printf("%s\n",key);
return 0;
}