fork download 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <numeric>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. // A struct to help with sorting suffixes in the doubling algorithm
  10. struct Suffix {
  11.     int index; // original index of suffix
  12.     int rank[2]; // ranks of the two halves
  13. };
  14.  
  15. // Custom comparison function for sorting Suffix structs
  16. int compareSuffixes(const Suffix& a, const Suffix& b) {
  17.     if (a.rank[0] != b.rank[0]) {
  18.         return a.rank[0] < b.rank[0];
  19.     }
  20.     return a.rank[1] < b.rank[1];
  21. }
  22.  
  23. // Function to build the Suffix Array using the doubling algorithm (O(n log n))
  24. vector<int> buildSuffixArray_doubling(const string& s) {
  25.     int n = s.length();
  26.     if (n == 0) return {};
  27.  
  28.     vector<Suffix> suffixes(n);
  29.     vector<int> suffix_array(n);
  30.     vector<int> new_rank(n);
  31.  
  32.     // Initial sort (prefixes of length 1)
  33.     for (int i = 0; i < n; ++i) {
  34.         suffixes[i].index = i;
  35.         suffixes[i].rank[0] = s[i] - 'a'; // Assuming lowercase English alphabet
  36.         suffixes[i].rank[1] = (i + 1 < n) ? (s[i + 1] - 'a') : -1;
  37.     }
  38.     sort(suffixes.begin(), suffixes.end(), compareSuffixes);
  39.  
  40.     // Iterative doubling
  41.     for (int k = 4; k < 2 * n; k *= 2) {
  42.         int rank_prev = 0;
  43.         suffixes[0].rank[0] = 0;
  44.         new_rank[suffixes[0].index] = 0;
  45.  
  46.         for (int i = 1; i < n; ++i) {
  47.             // Assign ranks for current length
  48.             if (suffixes[i].rank[0] == suffixes[i - 1].rank[0] &&
  49.                 suffixes[i].rank[1] == suffixes[i - 1].rank[1]) {
  50.                 rank_prev = suffixes[i].rank[0];
  51.                 suffixes[i].rank[0] = rank_prev;
  52.             } else {
  53.                 suffixes[i].rank[0] = suffixes[i - 1].rank[0] + 1;
  54.                 rank_prev = suffixes[i].rank[0];
  55.             }
  56.             new_rank[suffixes[i].index] = suffixes[i].rank[0];
  57.         }
  58.  
  59.         // Update second rank for the next iteration (length 2*k)
  60.         for (int i = 0; i < n; ++i) {
  61.             int next_index = suffixes[i].index + k / 2;
  62.             suffixes[i].rank[1] = (next_index < n) ? new_rank[next_index] : -1;
  63.         }
  64.  
  65.         sort(suffixes.begin(), suffixes.end(), compareSuffixes);
  66.     }
  67.  
  68.     for (int i = 0; i < n; ++i) {
  69.         suffix_array[i] = suffixes[i].index;
  70.     }
  71.  
  72.     return suffix_array;
  73. }
  74.  
  75. // Function to build the LCP array (already O(n))
  76. vector<int> buildLCPArray(const string& s, const vector<int>& suffix_array) {
  77.     int n = s.length();
  78.     if (n == 0) return {};
  79.  
  80.     vector<int> lcp(n - 1);
  81.     vector<int> rank(n);
  82.     for (int i = 0; i < n; ++i) {
  83.         rank[suffix_array[i]] = i;
  84.     }
  85.  
  86.     int h = 0;
  87.     for (int i = 0; i < n; ++i) {
  88.         if (rank[i] > 0) {
  89.             int j = suffix_array[rank[i] - 1];
  90.             if (h > 0) h--;
  91.             while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
  92.                 h++;
  93.             }
  94.             lcp[rank[i] - 1] = h;
  95.         }
  96.     }
  97.     return lcp;
  98. }
  99.  
  100. // Main function to count distinct substrings
  101. long long countDistinctSubstrings(const string& s) {
  102.     int n = s.length();
  103.     if (n == 0) return 0;
  104.  
  105.     // 1. Build the Suffix Array using the O(n log n) doubling algorithm
  106.     vector<int> suffix_array = buildSuffixArray_doubling(s);
  107.  
  108.     // 2. Build the LCP Array using Kasai's algorithm (O(n))
  109.     vector<int> lcp_array = buildLCPArray(s, suffix_array);
  110.  
  111.     // 3. Count distinct substrings using the formula
  112.     long long total_possible_substrings = static_cast<long long>(n) * (n + 1) / 2;
  113.     long long lcp_sum = accumulate(lcp_array.begin(), lcp_array.end(), 0LL);
  114.  
  115.     return total_possible_substrings - lcp_sum;
  116. }
  117.  
  118. int main() {
  119.     string s1 = "ababa";
  120.     cout << "The number of distinct substrings in '" << s1 << "' is: " 
  121.               << countDistinctSubstrings(s1) << endl;
  122.  
  123.     string s2 = "aaaaa";
  124.     cout << "The number of distinct substrings in '" << s2 << "' is: " 
  125.               << countDistinctSubstrings(s2) << endl;
  126.  
  127.     string s3 = "abcdefg";
  128.     cout << "The number of distinct substrings in '" << s3 << "' is: " 
  129.               << countDistinctSubstrings(s3) << endl;
  130.  
  131.     return 0;
  132. }
  133.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
adsdb
stdout 
The number of distinct substrings in 'ababa' is: 9
The number of distinct substrings in 'aaaaa' is: 5
The number of distinct substrings in 'abcdefg' is: 28
https://ideone.com/BiuV5I
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!