Distinct palindromic sub strings

I want to calculate number of DISTINCT palindromic substrings in a string.How to do it?
Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}
length of string could be 10^5 range.So i dont think O(n^2) solution will work.I want a algorithm to do this in less than O(n^2).

Questions by justacoder

Showing Answers 1 - 3 of 3 Answers

Eric Nantel

  • Apr 22nd, 2015
 

Code
  1. /*something like this*/

  2. bool isPalin = true;

  3. const char* msg;

  4. char* ptr_1 , ptr_2;

  5. ptr_1 = msg;

  6. unsigned int size = ARRAYSIZE(msg);

  7. ptr_2 = msg + (size - 1);

  8. auto sub;

  9. while(ptr_1 != ptr_2)

  10. {

  11.   if(*ptr_1 == *ptr_2)

  12.   {

  13.       sub.push(*ptr_1);

  14.    }

  15.    else  

  16.    {

  17.        isPalin = false;

  18.        break;

  19.    }

  20. }

  21.  

  22. /*there is probably mistake or a better way to do it for sure , but start with this*/

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions