How to find all the palindromes in a large array?-CodePudding

I need to find all the palindromes of π with 50 million digits 3.141592653589793238462643383279502884197169399375105820974944592307816406286... (goes on and on...)

I've stored all the digits of π in a char array. Now I need to search and count the number of 'palindromes' of length 2 to 15. For example, 535, 979, 33, 88, 14941, etc. are all valid results.

The final output I want is basically like the following.

Palindrome length           Number of Palindromes of this length
-----------------------------------------------------------------
   2                                  1234 (just an example)
   3                                  1245
   4                                  689
  ...                                 ...
  ...                                 ...
  ...                                 ...
  ...                                 ...
   15                                  0

pseudocode of my logic so far - it works but takes forever

//store all digits in a char array
char *piArray = (char *)malloc(NUM_PI_DIGITS * sizeof(char));
int count = 0; //count for the number of palindromes

//because we only need to find palindroms that are 2 - 15 digits long
for(int i = 2; i <= 15; i  ){
     //loop through the piArray and find all the palindromes with i digits long
     for(int j = 0; j < size_of_piArray; j  ){
            //check if the the sub array piArray[j:j i] is parlindrom, if so, add a count
            bool isPalindrome = true;
            for (int k = 0; k < i / 2; k  )
            {
                if (piArray [j   k] != piArray [j   i - 1 - k])
                {
                    isPalindrom = false;
                    break;
                }
            }
             if(isPalindrome){
                  count  ;
             }
     }
}

The problem I am facing now is that it takes too long to loop through the array of this large size (15-2)=13 times. Is there any better way to do this?

CodePudding user response：

I can't solve it for C, as I'm a C# dev but I expect the conversion will be trivial - I've tried to keep it as basic as possible

    char[] pi = "3.141592653589793238462643383279502884197169399375105820974944592307816406286".ToCharArray(); //get a small piece as an array of char
    int[] lenCounts = new int[16]; //make a new int array with slots 0-15
    
    for(int i = 1; i < pi.Length-1; i  ){

        if(pi[i 1] == pi[i-1]){ //center of an odd length pal
            int n = 2; 
            while(pi[i n] == pi[i-n] && n <= 7) n  ;
            lenCounts[((n-1)*2 1)]  ;
            
        } else if(pi[i] == pi[i-1]){ //center of an even length pal
            int n = 1;
            while(pi[i n] == pi[i-1-n] && n <= 7) n  ;
            lenCounts[n*2]  ;
            
        } 
            
            
    }

This demonstrates the "crawl the string looking for a palindrome center then crawl away from it in both directions looking for equal chars" technique..

..the only thing I'm not sure on, and it has occurred in the Pi posted, is what you want to do if palindromes overlap:

3.141592653589793238462643383279502884197169399375105820974944592307816406286

This contains 939 and overlapping with it, 3993. The algo above will find both, so if overlaps are not to be allowed then you might need to extend it to deal with eliminating earlier palindromes if they're overlapped by a longer one found later

You can play with the c# version at https://dotnetfiddle.net/tkQzBq - it has some debug print lines in too. Fiddles are limited to a 10 second execution time so I don't know if you'll be able to time the full 50 megabyte