Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <string>
- using namespace std;
- struct trie {
- char key;
- int count;
- trie *next, *child;
- };
- trie *make_trie(char key) {
- trie *ret = new trie;
- ret->key = key, ret->count = 0, ret->next = NULL, ret->child = NULL;
- return ret;
- }
- trie *trie_find(trie *root, string key) {
- trie *node, *list = root;
- for (size_t i = 0; i < key.size(); i++) {
- for (node = list; node != NULL; node = node->next) {
- if (node->key == key[i]) break;
- }
- if (node != NULL) {
- list = node->child;
- } else {
- return NULL;
- }
- }
- return (node->count > 0) ? node : NULL;
- }
- void trie_insert(trie *(&root), string key) {
- trie *node, *list = root, *parent = NULL;
- for (size_t i = 0; i < key.size(); i++) {
- for (node = list; node != NULL; node = node->next) {
- if (node->key == key[i]) break;
- }
- if (node != NULL) {
- list = node->child;
- } else {
- node = make_trie(key[i]);
- node->next = list;
- if (parent != NULL) {
- parent->child = node;
- } else {
- root = node;
- }
- list = NULL;
- }
- parent = node;
- }
- node->count++;
- }
- char buf[1024];
- string s, m;
- trie *t = NULL;
- int ans;
- int main() {
- freopen("unequal.in", "r", stdin);
- freopen("unequal.out", "w", stdout);
- scanf("%s", buf); s = string(buf);
- ans = 0;
- for (int i = 0; i < s.size(); i++) {
- for (int j = i; j < s.size(); j++) {
- m = s.substr(i, j - i + 1);
- if (trie_find(t, m) == NULL) {
- ans++; trie_insert(t, m);
- }
- }
- }
- printf("%d", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement