Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- using namespace std;
- typedef long long ll;
- class Trie {
- vector<vector<ll>> nodes;
- vector<bool> nodef;
- ll alphabetSize;
- public:
- Trie() {
- nodes.resize(1);
- alphabetSize = 26;
- nodes[0].resize(alphabetSize);
- }
- Trie(ll alphabetSize) {
- nodes.resize(1);
- this->alphabetSize = alphabetSize;
- nodes[0].resize(alphabetSize);
- }
- void insert(string word) {
- ll j = 0;
- for (ll i = 0; i < word.size(); i++) {
- if (nodes[j][word[i] - 'a'] == 0) {
- nodes.push_back(vector<ll>(alphabetSize, 0));
- nodes[j][word[i] - 'a'] = nodes.size() - 1;
- j = nodes.size() - 1;
- }
- else {
- j = nodes[j][word[i] - 'a'];
- }
- }
- nodef.resize(nodes.size());
- nodef[j] = true;
- }
- bool checkWord(string word) {
- ll j = 0;
- for (ll i = 0; i < word.size(); i++) {
- if (nodes[j][word[i] - 'a'] == 0) {
- return false;
- }
- j = nodes[j][word[i] - 'a'];
- }
- if (!nodef[j]) {
- return false;
- }
- return true;
- }
- ll size() {
- return nodes.size();
- }
- };
- int main() {
- Trie bor(26);
- ll n;
- cin >> n;
- for (ll i = 0; i < n; i++) {
- string a;
- cin >> a;
- bor.insert(a);
- }
- cout << bor.size() << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement