fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int P[200001]; // Longest Palidrome centered around position i
  6. int S[200001]; // Longest Palidrome that starts at position i "lower bound of the radius"
  7. int E[200001]; // Longest Palidrome that ends   at position i "upper bound of the radius"
  8. int Pr[200001];
  9. int N;
  10. int n;
  11. string s;
  12.  
  13. void manacher()
  14. {
  15.     N = 2*n + 1;
  16.     P[0] = 0;
  17.     E[0] = 0;
  18.  
  19.     int center = 0;
  20.     int centerRight = 0;
  21.     int i;
  22.  
  23.     int maxLPSLength = 0;
  24.     int maxLPSCenterPosition = 0;
  25.  
  26.     int distToEdge;
  27.  
  28.     for (i = 1; i < N; i++)
  29.     {
  30.         P[i] = 0;
  31.         distToEdge = centerRight - i;
  32.         if(distToEdge > 0) {
  33.             P[i] = min(P[center*2-i], distToEdge);
  34.             if(i-P[i] <= N/2)
  35.                 S[ i-P[i] ] = max(S[ i-P[i] ], P[i]);
  36.             if(i+P[i] >=  N/2)
  37.                 E[ i+P[i] ] = max(E[ i+P[i] ], P[i]);
  38.         }
  39.  
  40.         while
  41.         (
  42.         	(i + P[i] < N - 1) && (i - P[i] > 0) &&
  43. 			(
  44. 				( (i + P[i])&1 ) ||
  45. 				( s[(i+P[i])/2]==s[(i-P[i]-1)/2] )
  46. 			)
  47. 		)
  48.         {
  49.         	P[i]++;
  50.         	if(i-P[i] <= N/2)
  51.                 S[ i-P[i] ] = max(S[ i-P[i] ], P[i]);
  52.             if(i+P[i] >=  N/2)
  53.                 E[ i+P[i] ] = max(E[ i+P[i] ], P[i]);
  54.         }
  55.  
  56. 		if(P[i] > maxLPSLength) {
  57. 			maxLPSLength = P[i];
  58. 			maxLPSCenterPosition = i;
  59. 		}
  60.  
  61.         if (i + P[i] > centerRight) {
  62.         	center = i;
  63.             centerRight = i + P[i];
  64.         }
  65.     }
  66.  
  67.     Pr[N-1] = 0;
  68.     S[N-1] = 0;
  69.  
  70.     center = N-1;
  71.     int centerLeft = N-1;
  72.  
  73.     for (i = N-2; i >= 0; i--)
  74.     {
  75.         Pr[i] = 0;
  76.         distToEdge = i - centerLeft;
  77.         if(distToEdge > 0) {
  78.             Pr[i] = min(Pr[center*2-i], distToEdge);
  79.             if(i-Pr[i] > N/2)
  80.                 S[ i-Pr[i] ] = max(S[ i-Pr[i] ], Pr[i]);
  81.             if(i+Pr[i] <  N/2)
  82.                 E[ i+Pr[i] ] = max(E[ i+Pr[i] ], Pr[i]);
  83.         }
  84.  
  85.         while
  86.         (
  87.         	(i - Pr[i] > 0) && (i + Pr[i] < N - 1) &&
  88. 			(
  89. 				( (i - Pr[i])&1 ) ||
  90. 				( s[(i-Pr[i]-1)/2]==s[(i+Pr[i])/2] )
  91. 			)
  92. 		)
  93.         {
  94.             Pr[i]++;
  95.             if(i-Pr[i] > N/2)
  96.                 S[ i-Pr[i] ] = max(S[ i-Pr[i] ], Pr[i]);
  97.             if(i+Pr[i] <  N/2)
  98.                 E[ i+Pr[i] ] = max(E[ i+Pr[i] ], Pr[i]);
  99.         }
  100.  
  101.         if (i - Pr[i] > centerLeft) {
  102.         	center = i;
  103.             centerLeft = i + Pr[i];
  104.         }
  105.     }
  106.  
  107.     int start = (maxLPSCenterPosition - maxLPSLength)/2;
  108.     cout << "String:  " << s << '\n';
  109.     cout << "MString: #"; for(int i = 0; i < s.length(); i++) cout << s[i] << '#'; cout << '\n';
  110.     cout << "The Longest Palindromic Substring: " << s.substr(start, maxLPSLength) << '\n';
  111. }
  112.  
  113. int main() {
  114.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  115.  
  116.     s = "cbcbaaabc";
  117.     n = s.length();
  118.     manacher();
  119.  
  120.     cout << "The Longest Palindrome Length Starting at Every Index:\n";
  121.     for(int i = 0; i < n; i++)
  122.         cout << max(S[i*2], S[i*2+1]) << ' ';
  123.     cout << '\n';
  124.     cout << "The Longest Palindrome Length Ending at Every Index:\n";
  125.     for(int i = 0; i < n; i++)
  126.         cout << max(E[i*2+1], E[i*2+2]) << ' ';
  127.     cout << "\n\n";
  128.  
  129.     memset(P, 0, sizeof(P));
  130.     memset(Pr, 0, sizeof(Pr));
  131.     memset(S, 0, sizeof(S));
  132.     memset(E, 0, sizeof(E));
  133.     s = "cbcbbcc";
  134.     n = s.length();
  135.     manacher();
  136.  
  137.     cout << "The Longest Palindrome Length Starting at Every Index:\n";
  138.     for(int i = 0; i < n; i++)
  139.         cout << max(S[i*2], S[i*2+1]) << ' ';
  140.     cout << '\n';
  141.     cout << "The Longest Palindrome Length Ending at Every Index:\n";
  142.     for(int i = 0; i < n; i++)
  143.         cout << max(E[i*2+1], E[i*2+2]) << ' ';
  144.     cout << "\n\n";
  145.  
  146.     memset(P, 0, sizeof(P));
  147.     memset(Pr, 0, sizeof(Pr));
  148.     memset(S, 0, sizeof(S));
  149.     memset(E, 0, sizeof(E));
  150.     s = "dcbcbbcccbbcbc";
  151.     n = s.length();
  152.     manacher();
  153.  
  154.     cout << "The Longest Palindrome Length Starting at Every Index:\n";
  155.     for(int i = 0; i < n; i++)
  156.         cout << max(S[i*2], S[i*2+1]) << ' ';
  157.     cout << '\n';
  158.     cout << "The Longest Palindrome Length Ending at Every Index:\n";
  159.     for(int i = 0; i < n; i++)
  160.         cout << max(E[i*2+1], E[i*2+2]) << ' ';
  161.     cout << "\n\n";
  162.  
  163.     return 0;
  164. }
  165.  
Success #stdin #stdout 0s 18352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
String:  cbcbaaabc
MString: #c#b#c#b#a#a#a#b#c#
The Longest Palindromic Substring: cbaaabc
The Longest Palindrome Length Starting at Every Index:
3 3 7 5 3 2 1 1 1 
The Longest Palindrome Length Ending at Every Index:
1 1 3 3 1 2 3 5 7 

String:  cbcbbcc
MString: #c#b#c#b#b#c#c#
The Longest Palindromic Substring: cbbc
The Longest Palindrome Length Starting at Every Index:
3 3 4 2 1 2 1 
The Longest Palindrome Length Ending at Every Index:
1 1 3 3 2 4 2 

String:  dcbcbbcccbbcbc
MString: #d#c#b#c#b#b#c#c#c#b#b#c#b#c#
The Longest Palindromic Substring: cbcbbcccbbcbc
The Longest Palindrome Length Starting at Every Index:
1 13 11 9 7 5 3 2 4 2 3 3 1 1 
The Longest Palindrome Length Ending at Every Index:
1 1 1 3 3 2 4 2 3 5 7 9 11 13
https://ideone.com/kUywnA
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!