fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. pair<int, int> manacher(string s) {
  5. 	// assuming string is in the format of #s[1]#s[2]#...#s[n]# 
  6. 	// format with length larger than 3 (original unpadded string
  7. 	// has more than one char).
  8.  
  9. 	// preparation phase
  10. 	int* p = new int[s.size()]();
  11. 	p[0] = 1; p[1] = 2;
  12. 	int mx = 3;	// mx: store the index immediate after current
  13. 	            //longest palindrome
  14. 	int ind = 1; // ind: store current longest palindrome
  15. 	             //center index.
  16.  
  17. 	for (int i = 2; i < s.size(); i++) {
  18. 		// step1: precalculate p[i]
  19. 		if (i < mx) {
  20. 			int mirrorPi = p[2 * ind - i];
  21. 			int safePi = mx - i;
  22. 			p[i] = mirrorPi < safePi ? mirrorPi : safePi;
  23. 		}
  24. 		else {
  25. 			p[i] = 1;
  26. 		}
  27.  
  28. 		// step2: expand
  29. 		while (i + p[i] < s.size() \
  30. 			   && i - p[i] >= 0 \
  31. 			   && s[i + p[i]] == s[i - p[i]])
  32. 			p[i]++;
  33.  
  34. 		// step3: update mx and ind
  35. 		if (i + p[i] > mx) {
  36. 			mx = i + p[i];
  37. 			ind = i;
  38. 		}
  39. 	}
  40.  
  41. 	return make_pair(p[ind], ind);
  42. }
  43.  
  44.  
  45. int main() {
  46. 	string s = "#1#2#2#1#2#3#2#1#";
  47.  
  48. 	pair<int, int> p = manacher(s);
  49. 	cout << "radius is " << p.first << ", center at " << p.second << endl;
  50.  
  51.  	return 0;
  52. }
Success #stdin #stdout 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
radius is 6, center at 11
https://ideone.com/1h1KxC
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!