Advertisement
STANAANDREY

trie supl paa

Jun 3rd, 2024 (edited)
472
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.55 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <stdbool.h>
  5.  
  6. #define ALPHABET_SIZE (unsigned)('Z' - 'A' + 1)
  7. #define MAX_LEN 101
  8. #define TO_NR(c) (c - 'A')
  9. const char DICT_FILE[] = "dict.txt";
  10.  
  11. FILE* openFile(const char fname[], const char mode[]) {
  12.     FILE* file = fopen(fname, mode);
  13.     if (file == NULL) {
  14.         perror("");
  15.         exit(1);
  16.     }
  17.     return file;
  18. }
  19.  
  20. void closeFile(FILE* file) {
  21.     if (fclose(file) == -1) {
  22.         perror("");
  23.     }
  24. }
  25.  
  26. typedef struct TrieNode {
  27.     struct TrieNode* kids[ALPHABET_SIZE];
  28.     bool isWord;
  29. } TrieNode;
  30.  
  31. TrieNode* newNode() {
  32.     TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
  33.     if (node == NULL) {
  34.         perror("");
  35.         exit(1);
  36.     }
  37.     node->isWord = false;
  38.     memset(node->kids, NULL, ALPHABET_SIZE * sizeof(void*));
  39.     return node;
  40. }
  41.  
  42. typedef struct {
  43.     TrieNode* root;
  44. } Trie;
  45.  
  46. void init(Trie *trie) {
  47.     trie->root = newNode();
  48. }
  49.  
  50. void insert(Trie* trie, const char word[]) {
  51.     TrieNode* node = trie->root;
  52.     for (int i = 0; word[i]; i++) {
  53.         if (node->kids[TO_NR(word[i])] == NULL) {
  54.             node->kids[TO_NR(word[i])] = newNode();
  55.         }
  56.         node = node->kids[TO_NR(word[i])];
  57.     }
  58.     node->isWord = true;
  59. }
  60.  
  61. bool has(const Trie *const trie, const char word[]) {
  62.     TrieNode* node = trie->root;
  63.     for (int i = 0; word[i]; i++) {
  64.         node = node->kids[TO_NR(word[i])];
  65.         if (node == NULL) {
  66.             return false;
  67.         }
  68.     }
  69.     return node->isWord;
  70. }
  71.  
  72. void buildTrie(Trie *trie) {
  73.     FILE* f = openFile(DICT_FILE, "r");
  74.  
  75.     char word[MAX_LEN];
  76.     while (fgets(word, MAX_LEN, f)) {
  77.         word[strlen(word) - 1] = 0;
  78.         insert(trie, word);
  79.     }//*/
  80.  
  81.     closeFile(f);
  82. }
  83.  
  84. void swap(char* a, char* b) {
  85.     char tmp = *a;
  86.     *a = *b;
  87.     *b = tmp;
  88. }
  89.  
  90. void checkSwap(const Trie *const trie, const char word[]) {
  91.     for (int i = 0; word[i + 1]; i++) {
  92.         swap(&word[i], &word[i + 1]);
  93.         if (has(trie, word)) {
  94.             printf("%s ", word);
  95.         }
  96.         swap(&word[i], &word[i + 1]);
  97.     }
  98. }
  99.  
  100. void checkDoubled(const Trie* const trie, const char word[]) {
  101.     const size_t len = strlen(word);
  102.     for (size_t i = 0; i < len - 1; i++) {
  103.         if (word[i] == word[i + 1]) {
  104.             char auxWord[MAX_LEN] = { 0 };
  105.             strcpy_s(auxWord, sizeof(auxWord), word);
  106.             memmove(auxWord + i, auxWord + i + 1, len - i);
  107.             if (has(trie, auxWord)) {
  108.                 printf("%s ", auxWord);
  109.             }
  110.         }
  111.     }
  112. }
  113.  
  114. void checkMinus1(const Trie* const trie, const char word[]) {
  115.     char auxWord[MAX_LEN] = {0};
  116.     for (int i = 0; word[i]; i++) {
  117.         strncpy_s(auxWord, sizeof(auxWord), word, i);
  118.         strcpy_s(auxWord + i + 1, sizeof(auxWord) - i - 1, word + i);
  119.         for (char ch = 'A'; ch <= 'Z'; ch++) {
  120.             auxWord[i] = ch;
  121.             if (has(trie, auxWord)) {
  122.                 printf("%s ", auxWord);
  123.             }
  124.         }
  125.     }
  126. }
  127.  
  128. void query(const Trie* const trie) {
  129.     char word[MAX_LEN];
  130.     while (fgets(word, MAX_LEN, stdin)[1]) {
  131.         word[strlen(word) - 1] = 0;
  132.         const bool ok = has(trie, word);
  133.         printf("has: %d\n", ok);
  134.         if (!ok) {
  135.             printf("Suggestions: ");
  136.             checkSwap(trie, word);
  137.             checkDoubled(trie, word);
  138.             checkMinus1(trie, word);
  139.             putchar('\n');
  140.         }
  141.     }
  142. }
  143.  
  144. int main() {
  145.     Trie trie;
  146.     init(&trie);
  147.     buildTrie(&trie);
  148.     query(&trie);
  149.     return 0;
  150. }
  151.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement