Spaces:
Sleeping
Sleeping
| // Simplified suffix tree construction (Ukkonen's algorithm simulation) | |
| // For substring search and pattern matching | |
| typedef struct SuffixTreeNode { | |
| struct SuffixTreeNode *children[MAX_CHAR]; | |
| int start; | |
| int *end; | |
| int suffix_index; | |
| } SuffixTreeNode; | |
| typedef struct { | |
| char *text; | |
| SuffixTreeNode *root; | |
| int size; | |
| } SuffixTree; | |
| SuffixTreeNode* create_node(int start, int *end) { | |
| SuffixTreeNode *node = (SuffixTreeNode*)malloc(sizeof(SuffixTreeNode)); | |
| for (int i = 0; i < MAX_CHAR; i++) { | |
| node->children[i] = NULL; | |
| } | |
| node->start = start; | |
| node->end = end; | |
| node->suffix_index = -1; | |
| return node; | |
| } | |
| SuffixTree* create_suffix_tree(const char *text) { | |
| SuffixTree *tree = (SuffixTree*)malloc(sizeof(SuffixTree)); | |
| int len = strlen(text); | |
| tree->text = (char*)malloc(len + 1); | |
| strcpy(tree->text, text); | |
| tree->size = len; | |
| int *leaf_end = (int*)malloc(sizeof(int)); | |
| *leaf_end = -1; | |
| tree->root = create_node(-1, leaf_end); | |
| // Simplified construction - add suffixes directly | |
| for (int i = 0; i < len; i++) { | |
| SuffixTreeNode *curr = tree->root; | |
| for (int j = i; j < len; j++) { | |
| unsigned char c = text[j]; | |
| if (!curr->children[c]) { | |
| int *end = (int*)malloc(sizeof(int)); | |
| *end = len - 1; | |
| curr->children[c] = create_node(j, end); | |
| curr->children[c]->suffix_index = i; | |
| break; | |
| } | |
| curr = curr->children[c]; | |
| } | |
| } | |
| return tree; | |
| } | |
| int search_pattern(SuffixTree *tree, const char *pattern) { | |
| int len = strlen(pattern); | |
| SuffixTreeNode *curr = tree->root; | |
| for (int i = 0; i < len; i++) { | |
| unsigned char c = pattern[i]; | |
| if (!curr->children[c]) { | |
| return 0; | |
| } | |
| curr = curr->children[c]; | |
| } | |
| return 1; | |
| } | |
| void free_suffix_tree(SuffixTreeNode *node) { | |
| if (!node) return; | |
| for (int i = 0; i < MAX_CHAR; i++) { | |
| if (node->children[i]) { | |
| free_suffix_tree(node->children[i]); | |
| } | |
| } | |
| if (node->end) { | |
| free(node->end); | |
| } | |
| free(node); | |
| } | |
| void generate_text(char *text, int size) { | |
| unsigned int seed = 42; | |
| for (int i = 0; i < size - 1; i++) { | |
| seed = seed * 1103515245 + 12345; | |
| text[i] = 'a' + (seed % 4); // Small alphabet | |
| } | |
| text[size - 1] = '\0'; | |
| } | |
| int main() { | |
| char *text = (char*)malloc(TEXT_SIZE); | |
| generate_text(text, TEXT_SIZE); | |
| clock_t start = clock(); | |
| SuffixTree *tree = create_suffix_tree(text); | |
| int matches = 0; | |
| for (int i = 0; i < NUM_PATTERNS; i++) { | |
| // Search for substrings from the text | |
| int pos = (i * 17) % (TEXT_SIZE - 10); | |
| char pattern[11]; | |
| strncpy(pattern, text + pos, 10); | |
| pattern[10] = '\0'; | |
| if (search_pattern(tree, pattern)) { | |
| matches++; | |
| } | |
| } | |
| clock_t end = clock(); | |
| double time_spent = (double)(end - start) / CLOCKS_PER_SEC; | |
| printf("Suffix tree: text=%d, %d searches, %.6f seconds\n", | |
| TEXT_SIZE, NUM_PATTERNS, time_spent); | |
| printf("Matches found: %d\n", matches); | |
| free_suffix_tree(tree->root); | |
| free(tree->text); | |
| free(tree); | |
| free(text); | |
| return 0; | |
| } | |