diff options
author | Franciszek Malinka <franciszek.malinka@gmail.com> | 2021-02-25 14:42:55 +0100 |
---|---|---|
committer | Franciszek Malinka <franciszek.malinka@gmail.com> | 2021-02-25 14:42:55 +0100 |
commit | 9477dbe667f250ecd23f8fc0d56b942191526421 (patch) | |
tree | a4b50c9a726f415f835f5311c11c5d66e95f688c /Semestr 3/pf/lista7/zaj.cpp | |
parent | 1968c1e590077bd51844eacfac722d7963848cb8 (diff) |
Stare semestry, niepoukladane
Diffstat (limited to 'Semestr 3/pf/lista7/zaj.cpp')
-rw-r--r-- | Semestr 3/pf/lista7/zaj.cpp | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/Semestr 3/pf/lista7/zaj.cpp b/Semestr 3/pf/lista7/zaj.cpp new file mode 100644 index 0000000..403754f --- /dev/null +++ b/Semestr 3/pf/lista7/zaj.cpp @@ -0,0 +1,80 @@ +#include <bits/stdc++.h> +using namespace std; + +const int ALPHABET_SIZE = 26; + +struct node +{ + node *children[ALPHABET_SIZE]; + int cnt; + bool is_end; + + node() + { + for (int i = 0; i < ALPHABET_SIZE; i++) + children[i] = nullptr; + is_end = false; + cnt = 0; + } +}; + +struct TRIE +{ + node *root; + + TRIE() + { + root = new node; + } + + // dodaje słowo do słownika + void add_word(string word) + { + node *crawl = root; + for (auto c : word) + { + int letter = c - 'a'; + if (crawl->children[letter] == nullptr) + { + crawl->children[letter] = new node; + } + crawl = crawl->children[letter]; + } + crawl->is_end = true; + } + + // sprawdź czy słowo jest w słowniku + bool find(string word) + { + node *crawl = root; + for (auto c : word) + { + int letter = c - 'a'; + if (crawl->children[letter] == nullptr) + return false; + crawl = crawl->children[letter]; + } + return crawl->is_end; + } + + // usuń słowo ze słownika + void erase(string word) {} +}; + +int main() +{ + TRIE dictionary; + int q; + cin >> q; + while (q--) + { + char c; + string s; + cin >> c >> s; + if (c == 'A') + dictionary.add_word(s); + else + cout << (dictionary.find(s) ? "TAK" : "NIE") + << "\n"; + } +}
\ No newline at end of file |