Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <stdbool.h>
- #define ALPHABET_SIZE (unsigned)('Z' - 'A' + 1)
- #define MAX_LEN 101
- #define TO_NR(c) (c - 'A')
- const char DICT_FILE[] = "dict.txt";
- FILE* openFile(const char fname[], const char mode[]) {
- FILE* file = fopen(fname, mode);
- if (file == NULL) {
- perror("");
- exit(1);
- }
- return file;
- }
- void closeFile(FILE* file) {
- if (fclose(file) == -1) {
- perror("");
- }
- }
- typedef struct TrieNode {
- struct TrieNode* kids[ALPHABET_SIZE];
- bool isWord;
- } TrieNode;
- TrieNode* newNode() {
- TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
- if (node == NULL) {
- perror("");
- exit(1);
- }
- node->isWord = false;
- memset(node->kids, NULL, ALPHABET_SIZE * sizeof(void*));
- return node;
- }
- typedef struct {
- TrieNode* root;
- } Trie;
- void init(Trie *trie) {
- trie->root = newNode();
- }
- void insert(Trie* trie, const char word[]) {
- TrieNode* node = trie->root;
- for (int i = 0; word[i]; i++) {
- if (node->kids[TO_NR(word[i])] == NULL) {
- node->kids[TO_NR(word[i])] = newNode();
- }
- node = node->kids[TO_NR(word[i])];
- }
- node->isWord = true;
- }
- bool has(const Trie *const trie, const char word[]) {
- TrieNode* node = trie->root;
- for (int i = 0; word[i]; i++) {
- node = node->kids[TO_NR(word[i])];
- if (node == NULL) {
- return false;
- }
- }
- return node->isWord;
- }
- void buildTrie(Trie *trie) {
- FILE* f = openFile(DICT_FILE, "r");
- char word[MAX_LEN];
- while (fgets(word, MAX_LEN, f)) {
- word[strlen(word) - 1] = 0;
- insert(trie, word);
- }//*/
- closeFile(f);
- }
- void swap(char* a, char* b) {
- char tmp = *a;
- *a = *b;
- *b = tmp;
- }
- void checkSwap(const Trie *const trie, const char word[]) {
- for (int i = 0; word[i + 1]; i++) {
- swap(&word[i], &word[i + 1]);
- if (has(trie, word)) {
- printf("%s ", word);
- }
- swap(&word[i], &word[i + 1]);
- }
- }
- void checkDoubled(const Trie* const trie, const char word[]) {
- const size_t len = strlen(word);
- for (size_t i = 0; i < len - 1; i++) {
- if (word[i] == word[i + 1]) {
- char auxWord[MAX_LEN] = { 0 };
- strcpy_s(auxWord, sizeof(auxWord), word);
- memmove(auxWord + i, auxWord + i + 1, len - i);
- if (has(trie, auxWord)) {
- printf("%s ", auxWord);
- }
- }
- }
- }
- void checkMinus1(const Trie* const trie, const char word[]) {
- char auxWord[MAX_LEN] = {0};
- for (int i = 0; word[i]; i++) {
- strncpy_s(auxWord, sizeof(auxWord), word, i);
- strcpy_s(auxWord + i + 1, sizeof(auxWord) - i - 1, word + i);
- for (char ch = 'A'; ch <= 'Z'; ch++) {
- auxWord[i] = ch;
- if (has(trie, auxWord)) {
- printf("%s ", auxWord);
- }
- }
- }
- }
- void query(const Trie* const trie) {
- char word[MAX_LEN];
- while (fgets(word, MAX_LEN, stdin)[1]) {
- word[strlen(word) - 1] = 0;
- const bool ok = has(trie, word);
- printf("has: %d\n", ok);
- if (!ok) {
- printf("Suggestions: ");
- checkSwap(trie, word);
- checkDoubled(trie, word);
- checkMinus1(trie, word);
- putchar('\n');
- }
- }
- }
- int main() {
- Trie trie;
- init(&trie);
- buildTrie(&trie);
- query(&trie);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement