[text] Number of distinct substrings

Viewer

copydownloadembedprintName: Number of distinct substrings
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define fr(i,n) for(ll i=0;i<n;i++)
  6. struct node
  7. {
  8.     ll cnt;
  9.     struct node* child[26];
  10.     node()
  11.     {
  12.         cnt=0;
  13.         fr(i,26)child[i]=NULL;
  14.     }
  15. };
  16. struct trie
  17. {
  18.     node* root;
  19.     trie()
  20.     {
  21.         root =new node();
  22.     }
  23. };
  24. trie *rt;
  25. ll ans;
  26. string s;
  27. void insert(ll i)
  28. {
  29.     node* cur=rt->root;
  30.     while(i<s.size())
  31.     {
  32.         if(cur->child[s[i]-'a']==NULL){cur->child[s[i]-'a']=new node();ans++;}
  33.         cur=cur->child[s[i]-'a'];
  34.         i++;
  35.     }
  36. }
  37. void solve()
  38. {
  39.     ans=1;
  40.     cin>>s;
  41.     rt=new trie();
  42.     fr(i,s.size())
  43.     {
  44.         insert(i);
  45.     }
  46.     //including empty substring 
  47.     cout<<ans<<en;
  48. }
  49.  
  50. int main()
  51. {
  52.     fast
  53.     // ll t;cin>>t;while(t--)
  54.     solve();
  55.     return 0;
  56. }

Editor

You can edit this paste and save as new:


File Description
  • Number of distinct substrings
  • Paste Code
  • 08 Jul-2022
  • 908 Bytes
You can Share it: