fork download
copy 
  1. // A C program to implement Manacher’s Algorithm
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. string text;
  6. void findLongestPalindromicString()
  7. {
  8.     int N = text.length();
  9.     if(N == 0)
  10.         return;
  11.     N = 2*N + 1; //Position count
  12.     int L[N]; //LPS Length Array
  13.     L[0] = 0;
  14.     L[1] = 1;
  15.     int C = 1; //centerPosition 
  16.     int R = 2; //centerRightPosition
  17.     int i = 0; //currentRightPosition
  18.     int iMirror; //currentLeftPosition
  19.     int expand = -1;
  20.     int diff = -1;
  21.     int maxLPSLength = 0;
  22.     int maxLPSCenterPosition = 0;
  23.     int start = -1;
  24.     int end = -1;
  25.  
  26.     //Uncomment it to print LPS Length array
  27.     //printf("%d %d ", L[0], L[1]);
  28.     for (i = 2; i < N; i++) 
  29.     {
  30.         //get currentLeftPosition iMirror for currentRightPosition i
  31.         iMirror  = 2*C-i;
  32.         //Reset expand - means no expansion required
  33.         expand = 0;
  34.         diff = R - i;
  35.         //If currentRightPosition i is within centerRightPosition R
  36.         if(diff > 0) 
  37.         {
  38.             if(L[iMirror] < diff) // Case 1
  39.                 L[i] = L[iMirror];
  40.             else if(L[iMirror] == diff && i == N-1) // Case 2
  41.                 L[i] = L[iMirror];
  42.             else if(L[iMirror] == diff && i < N-1)  // Case 3
  43.             {
  44.                     L[i] = L[iMirror];
  45.                     expand = 1;  // expansion required
  46.             }
  47.             else if(L[iMirror] > diff)  // Case 4
  48.             {
  49.                 L[i] = diff;
  50.                 expand = 1;  // expansion required
  51.             }
  52.         }
  53.         else
  54.         {
  55.             L[i] = 0;
  56.             expand = 1;  // expansion required
  57.         }
  58.  
  59.         if (expand == 1)
  60.         {
  61.             //Attempt to expand palindrome centered at currentRightPosition i
  62.             //Here for odd positions, we compare characters and 
  63.             //if match then increment LPS Length by ONE
  64.             //If even position, we just increment LPS by ONE without 
  65.             //any character comparison
  66.             while (((i + L[i]) < N && (i - L[i]) > 0) && 
  67.                 ( ((i + L[i] + 1) % 2 == 0) || 
  68.                 (text[(i + L[i] + 1)/2] == text[(i-L[i]-1)/2] )))
  69.             {
  70.                 L[i]++;
  71.             }
  72.         }
  73.  
  74.         if(L[i] > maxLPSLength)  // Track maxLPSLength
  75.         {
  76.             maxLPSLength = L[i];
  77.             maxLPSCenterPosition = i;
  78.         }
  79.  
  80.         // If palindrome centered at currentRightPosition i 
  81.         // expand beyond centerRightPosition R,
  82.         // adjust centerPosition C based on expanded palindrome.
  83.         if (i + L[i] > R) 
  84.         {
  85.             C = i;
  86.             R = i + L[i];
  87.         }
  88.         //Uncomment it to print LPS Length array
  89.         //printf("%d ", L[i]);
  90.     }
  91.     //printf("\n");
  92.     start = (maxLPSCenterPosition - maxLPSLength)/2;
  93.     end = start + maxLPSLength - 1;
  94.     printf("start: %d end: %d\n", start, end);
  95.     printf("LPS of string is %s : ", text);
  96.     for(i=start; i<=end; i++)
  97.         printf("%c", text[i]);
  98.     printf("\n");
  99. }
  100.  
  101.  
  102. int main(int argc, char *argv[])
  103. {
  104.  
  105.     text= "daiict"; //strcpy(text, "daiict");
  106.     findLongestPalindromicString();
  107. }
Compilation error #stdin compilation error #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:5:1: error: ‘string’ does not name a type
 string text;
 ^~~~~~
prog.cpp: In function ‘void findLongestPalindromicString()’:
prog.cpp:8:13: error: ‘text’ was not declared in this scope
     int N = text.length();
             ^~~~
prog.cpp: In function ‘int main(int, char**)’:
prog.cpp:105:5: error: ‘text’ was not declared in this scope
     text= "daiict"; //strcpy(text, "daiict");
     ^~~~
stdout
copy 
Standard output is empty
https://ideone.com/RlrGOh
language:
C++14 (gcc 8.3)
created:
7 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!