Advertisement
Guest User

Untitled

a guest
Jul 27th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.84 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. struct trie {
  8. char key;
  9. int count;
  10. trie *next, *child;
  11. };
  12.  
  13. trie *make_trie(char key) {
  14. trie *ret = new trie;
  15. ret->key = key, ret->count = 0, ret->next = NULL, ret->child = NULL;
  16. return ret;
  17. }
  18.  
  19. trie *trie_find(trie *root, string key) {
  20. trie *node, *list = root;
  21. for (size_t i = 0; i < key.size(); i++) {
  22. for (node = list; node != NULL; node = node->next) {
  23. if (node->key == key[i]) break;
  24. }
  25. if (node != NULL) {
  26. list = node->child;
  27. } else {
  28. return NULL;
  29. }
  30. }
  31. return (node->count > 0) ? node : NULL;
  32. }
  33.  
  34. void trie_insert(trie *(&root), string key) {
  35. trie *node, *list = root, *parent = NULL;
  36. for (size_t i = 0; i < key.size(); i++) {
  37. for (node = list; node != NULL; node = node->next) {
  38. if (node->key == key[i]) break;
  39. }
  40. if (node != NULL) {
  41. list = node->child;
  42. } else {
  43. node = make_trie(key[i]);
  44. node->next = list;
  45. if (parent != NULL) {
  46. parent->child = node;
  47. } else {
  48. root = node;
  49. }
  50. list = NULL;
  51. }
  52. parent = node;
  53. }
  54. node->count++;
  55. }
  56.  
  57. char buf[1024];
  58. string s, m;
  59. trie *t = NULL;
  60. int ans;
  61.  
  62. int main() {
  63. freopen("unequal.in", "r", stdin);
  64. freopen("unequal.out", "w", stdout);
  65.  
  66. scanf("%s", buf); s = string(buf);
  67.  
  68. ans = 0;
  69.  
  70. for (int i = 0; i < s.size(); i++) {
  71. for (int j = i; j < s.size(); j++) {
  72. m = s.substr(i, j - i + 1);
  73. if (trie_find(t, m) == NULL) {
  74. ans++; trie_insert(t, m);
  75. }
  76. }
  77. }
  78.  
  79. printf("%d", ans);
  80.  
  81. return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement