fork download
copy 
  1. // C++ program to find all distinct palindrome sub-strings
  2. // of a given string
  3. #include <iostream>
  4. #include <map>
  5. using namespace std;
  6.  
  7. // Function to print all distinct palindrome sub-strings of s
  8. int palindromeSubStrs(string s)
  9. {
  10.     map<string, int> m;
  11.     int n = s.size();
  12.  
  13.     // table for storing results (2 rows for odd-
  14.     // and even-length palindromes
  15.     int R[2][n+1];
  16.  
  17.     // Find all sub-string palindromes from the given input
  18.     // string insert 'guards' to iterate easily over s
  19.     s = "@" + s + "#";
  20.  
  21.     for (int j = 0; j <= 1; j++)
  22.     {
  23.         int rp = 0;   // length of 'palindrome radius'
  24.         R[j][0] = 0;
  25.  
  26.         int i = 1;
  27.         while (i <= n)
  28.         {
  29.             //  Attempt to expand palindrome centered at i
  30.             while (s[i - rp - 1] == s[i + j + rp])
  31.                 rp++;  // Incrementing the length of palindromic
  32.                        // radius as and when we find vaid palindrome
  33.  
  34.             // Assigning the found palindromic length to odd/even
  35.             // length array
  36.             R[j][i] = rp;
  37.             int k = 1;
  38.             while ((R[j][i - k] != rp - k) && (k < rp))
  39.             {
  40.                 R[j][i + k] = min(R[j][i - k],rp - k);
  41.                 k++;
  42.             }
  43.             rp = max(rp - k,0);
  44.             i += k;
  45.         }
  46.     }
  47.  
  48.     // remove 'guards'
  49.     s = s.substr(1, n);
  50.  
  51.     // Put all obtained palindromes in a hash map to
  52.     // find only distinct palindromess
  53.     m[string(1, s[0])]=1;
  54.     for (int i = 1; i <= n; i++)
  55.     {
  56.         for (int j = 0; j <= 1; j++)
  57.             for (int rp = R[j][i]; rp > 0; rp--)
  58.                m[s.substr(i - rp - 1, 2 * rp + j)]=1;
  59.         m[string(1, s[i])]=1;
  60.     }
  61.  
  62.     //printing all distinct palindromes from hash map
  63.    return (m.size()-1);
  64. }
  65.  
  66. // Driver program
  67. int main() {
  68.     ofstream fout(getenv("OUTPUT_PATH"));
  69.     int res;
  70.     string _str;
  71.     getline(cin, _str);
  72.  
  73.     res = palindromeSubStrs(_str);
  74.     fout << res << endl;
  75.  
  76.     fout.close();
  77.     return 0;
  78. }
Compilation error #stdin compilation error #stdout 0s 4136KB
comments (?)
stdin
copy 
abaaa
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:68:19: error: variable 'std::ofstream fout' has initializer but incomplete type
     ofstream fout(getenv("OUTPUT_PATH"));
                   ^
stdout
copy 
Standard output is empty
https://ideone.com/8OIZ9S
language:
C++14 (gcc 8.3)
created:
10 years 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!