title: Frequency of all substrings
body: <p>I want to find frequency of all substrings in a string in C++. Currently I am using the following :</p>
  
  <pre><code>    unordered_map&lt;string,int&gt; mp;
      string s;// the string of which we want all substrings... n is length
      cin&gt;&gt;s;
      string t;
      for(int i=0,i&lt;=n-1;++i) // starting point of a substring
      {
          t="";
          for(int j=i;j&lt;=n-1;++j) // all substrings startings at i
          {
              t+=s[j];
              ++mp[t];
          }
      }
  </code></pre>
  
  <p>I want to improve its time complexity. Can we do any better? Does there exist a better algorithm? Sorry if this is not on topic here... I will close it if that's the case.</p>
  
  <p><strong>Edit :</strong></p>
  
  <p>Here's what I came up with... Maintain a trie of all suffixes of the string. Then traverse all the substrings starting at i so that searching is O(1).</p>
  
  <p>Each node specifies a substring(prefix of suffix). Now maintain frequency at each node and update it accordingly. Though this method is O(n^2) but the constants are fairly large due to memory allocation and resetting each next pointers of node(26 times) to NULL. Can I optimize it further? Also can there be any faster alternatives to store a trie than a linked list? I was able to squeeze my solution but it was very close to the time limit.</p>