Salvens

A

Aug 10th, 2023
702
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8.  
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #pragma comment(linker,"/STACK:1000000000,1000000000")
  14.  
  15. const long long INF = 1e9 + 7;
  16. const int MAXN = 1e4 + 5;
  17. const int N = 1e5 + 10;
  18.  
  19. struct vertex {
  20.     int next[26];
  21.     bool terminal = false;
  22. } v[MAXN];
  23.  
  24. int root = 0, top = 1;
  25.  
  26. void add(const string& s) {
  27.     int cur = root;
  28.     for (auto& i: s) {
  29.         int x = i - 'a';
  30.         if (v[cur].next[x] == 0) {
  31.             v[cur].next[x] = top++;
  32.         }
  33.         cur = v[cur].next[x];
  34.     }
  35.     v[cur].terminal = true;
  36. }
  37.  
  38. signed main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr);
  41.     cout.tie(nullptr);
  42.  
  43.     string s;
  44.     cin >> s;
  45.     int n = s.size();
  46.     for (int len = 1; len <= n; ++len) {
  47.         for (int l = 0; l + len - 1 < n; ++l) {
  48.             add(s.substr(l, len));
  49.         }
  50.     }
  51.  
  52.     int ans = 0;
  53.     for (int i = 0; i < top; ++i) {
  54.         ans += v[i].terminal;
  55.     }
  56.     cout << ans << '\n';
  57. }
Advertisement
Add Comment
Please, Sign In to add comment