Code: Select all
#include <iostream>
#include <cmath>
#include <string.h>
#include <vector>
#include <cstdlib>
#include <cstdio>
using namespace std;
#define HASH_TABLE_SIZE 75000
#define WHITE 0
#define GRAY 1
#define BLACK 2
typedef struct hash_table_t_st{
int wordIndex;
struct hash_table_t_st *next;
}hash_table_t;
char **dict;
int n;
hash_table_t **hash_table;
int conflicts=0;
vector<int> *adjacency_list;
int *vertex_color;
int max_esl=0;
void insert_hash_table(int hash_index, int wordIndex)
{
hash_table_t *temp;
if(hash_table[hash_index]==NULL)
{
hash_table[hash_index] = (hash_table_t *) calloc(1, sizeof(hash_table_t));
hash_table[hash_index]->wordIndex = wordIndex;
hash_table[hash_index]->next = NULL;
}
else
{
temp = hash_table[hash_index];
hash_table[hash_index] = (hash_table_t *) calloc(1, sizeof(hash_table_t));
hash_table[hash_index]->wordIndex = wordIndex;
hash_table[hash_index]->next = temp;
conflicts++;
}
}
void hash_word(int wordIndex)
{
unsigned int iter=0, hash_index, value=0;
int shift=6;
unsigned int mask = ~0U << (8*sizeof(unsigned int) - shift);
while(dict[wordIndex][iter])
{
value = (value & mask) ^ (value << shift) ^ dict[wordIndex][iter];
iter++;
}
hash_index = (value%HASH_TABLE_SIZE);
insert_hash_table(hash_index, wordIndex);
}
void hash_dict()
{
for(int i=0; i<n; i++)
hash_word(i);
}
void print_dict()
{
for(int i=0; i<n; i++)
cout << dict[i] << endl;
}
void draw_edge(int v1, int v2)
{
adjacency_list[v1].push_back(v2);
}
int get_index(char *word)
{
hash_table_t *h_iter;
unsigned int iter=0, hash_index, value=0;
int shift=6;
unsigned int mask = ~0U << (8*sizeof(unsigned int) - shift);
while(word[iter])
{
value = (value & mask) ^ (value << shift) ^ word[iter];
iter++;
}
hash_index = (value%HASH_TABLE_SIZE);
h_iter = hash_table[hash_index];
if(h_iter == NULL)
return -1;
else
while(h_iter)
{
if(strcmp(dict[h_iter->wordIndex], word) == 0)
return h_iter->wordIndex;
else
h_iter = h_iter->next;
}
return -1;
}
void compute_edit_step_chain(int index)
{
char add_edit_step[16], sub_edit_step[16], change_edit_step[16];
int iter=0;
const int len=strlen(dict[index]);
int i, idx;
for(int pos=0; pos<len; pos++)
{
if(len < 16)
{
for(i=0; i<26; i++)
{
memset((char *) add_edit_step, '\0', 16);
strncpy((char *) &add_edit_step,dict[index], pos);
add_edit_step[pos] = char(97+i);
strncat((char *) &add_edit_step[pos+1], (char *) &dict[index][pos], len-pos);
idx = get_index((char *) add_edit_step);
if(idx>=0)
draw_edge(index, idx);
}
}
if(len > 0)
{
memset((char *) sub_edit_step, '\0', 16);
strncpy((char *) &sub_edit_step, dict[index], pos);
strncat((char *) &sub_edit_step[pos], (char *) &dict[index][pos+1], len-(pos+1));
idx = get_index((char *) sub_edit_step);
if(idx>=0)
draw_edge(index, idx);
}
for(i=0; i<26; i++)
{
memset((char *) change_edit_step, '\0', 16);
strcpy((char *) &change_edit_step, dict[index]);
if(change_edit_step[pos]!=char(97+i))
{
change_edit_step[pos]=char(97+i);
idx = get_index((char *) change_edit_step);
if(idx>=0)
draw_edge(index, idx);
}
}
}
}
int dfs(int vertex)
{
vertex_color[vertex] = GRAY;
int max_depth=1, depth=1, i=0, iter=0;
do
{
iter = (adjacency_list[vertex])[i];
if(vertex_color[iter]==WHITE)
depth+= dfs(iter);
max_depth>?=depth;
i++;
}while(i < adjacency_list[vertex].size());
vertex_color[vertex] = BLACK;
return max_depth;
}
void compute_longest_esl()
{
for(int i=0; i<n; i++)
{
if(adjacency_list[i].empty())
compute_edit_step_chain(i);
}
for(int i=0; i<n; i++)
{
if(adjacency_list[i].empty())
vertex_color[i]=BLACK;
else if(vertex_color[i] == WHITE)
max_esl >?= dfs(i);
}
}
int main()
{
n=0;
char inp[16];
hash_table = (hash_table_t **) calloc (HASH_TABLE_SIZE, sizeof(hash_table_t *));
dict = (char **) calloc(25000, sizeof(char *));
while (cin >> inp)
{
dict[n]=(char *) calloc(strlen(inp),sizeof(char));
strcpy(dict[n],inp);
n++;
}
vertex_color = (int *) calloc(n, sizeof(int));
adjacency_list = (vector<int> *) calloc(n, sizeof(vector<int>));
hash_dict();
compute_longest_esl();
if(max_esl > 0)
cout << max_esl-1 << endl;
else
cout << 0;
for(int i=0;i<n;i++)
free(dict[i]);
free(dict);
free(adjacency_list);
free(vertex_color);
return 0;
}
