Advertisement
EzicMan

BOR

Dec 11th, 2018
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. class Trie {
  9. vector<vector<ll>> nodes;
  10. vector<bool> nodef;
  11. ll alphabetSize;
  12. public:
  13. Trie() {
  14. nodes.resize(1);
  15. alphabetSize = 26;
  16. nodes[0].resize(alphabetSize);
  17. }
  18. Trie(ll alphabetSize) {
  19. nodes.resize(1);
  20. this->alphabetSize = alphabetSize;
  21. nodes[0].resize(alphabetSize);
  22. }
  23. void insert(string word) {
  24. ll j = 0;
  25. for (ll i = 0; i < word.size(); i++) {
  26. if (nodes[j][word[i] - 'a'] == 0) {
  27. nodes.push_back(vector<ll>(alphabetSize, 0));
  28. nodes[j][word[i] - 'a'] = nodes.size() - 1;
  29. j = nodes.size() - 1;
  30. }
  31. else {
  32. j = nodes[j][word[i] - 'a'];
  33. }
  34. }
  35. nodef.resize(nodes.size());
  36. nodef[j] = true;
  37. }
  38. bool checkWord(string word) {
  39. ll j = 0;
  40. for (ll i = 0; i < word.size(); i++) {
  41. if (nodes[j][word[i] - 'a'] == 0) {
  42. return false;
  43. }
  44. j = nodes[j][word[i] - 'a'];
  45. }
  46. if (!nodef[j]) {
  47. return false;
  48. }
  49. return true;
  50. }
  51. ll size() {
  52. return nodes.size();
  53. }
  54. };
  55.  
  56. int main() {
  57. Trie bor(26);
  58. ll n;
  59. cin >> n;
  60. for (ll i = 0; i < n; i++) {
  61. string a;
  62. cin >> a;
  63. bor.insert(a);
  64. }
  65. cout << bor.size() << endl;
  66. return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement