fork download
copy 
  1. #include<cstring>
  2. #include<stdio.h>
  3. #include<algorithm>
  4. #include<string>
  5. #include<iostream>
  6.  
  7. using namespace std;
  8.  
  9.  
  10. bool ISpal(string s)
  11. {
  12. 	string t = s;
  13. 	reverse(t.begin(), t.end());
  14. 	return t == s;
  15. }
  16.  
  17. string preProcess(string s) {
  18. 	int n = s.length();
  19. 	if (n == 0) return "^$";
  20. 	string ret = "^";
  21. 	for (int i = 0; i < n; i++)
  22. 		ret += "#" + s.substr(i, 1);
  23.  
  24. 	ret += "#$";
  25. 	return ret;
  26. }
  27.  
  28. string longestPalindrome(string s) {
  29. 	string T = preProcess(s);
  30. 	int n = T.length();
  31. 	int *P = new int[n];
  32. 	int C = 0, R = 0;
  33. 	for (int i = 1; i < n - 1; i++) {
  34. 		int i_mirror = 2 * C - i; // equals to i' = C - (i-C)
  35.  
  36. 		P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;
  37.  
  38. 		// Attempt to expand palindrome centered at i
  39. 		while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
  40. 			P[i]++;
  41.  
  42. 		// If palindrome centered at i expand past R,
  43. 		// adjust center based on expanded palindrome.
  44. 		if (i + P[i] > R) {
  45. 			C = i;
  46. 			R = i + P[i];
  47. 		}
  48. 	}
  49.  
  50. 	// Find the maximum element in P.
  51. 	int maxLen = 0;
  52. 	int centerIndex = 0;
  53. 	for (int i = 1; i < n - 1; i++) {
  54. 		if (P[i] >= maxLen) {
  55. 			maxLen = P[i];
  56. 			centerIndex = i;
  57. 		}
  58. 	}
  59.  
  60. 	delete[] P;
  61.  
  62. 	return s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
  63. }
  64.  
  65. char s[100001];
  66. int main()
  67. {
  68. //	freopen("in.in", "r", stdin);
  69. //	freopen("out.out", "w", stdout);
  70. 	while (cin >> s)
  71. 	{
  72. 		string os(s);
  73. 		if (!ISpal(os))
  74. 		{
  75. 			int cen = os.length() - 1;
  76. 			string pal = longestPalindrome(os);
  77. 			int l = pal.length();
  78. 			int f = os.find(pal);
  79. 			string b_pal = os.substr(0, f);//before pal
  80. 			string a_pal = os.substr(f + l);//after pal
  81. 			reverse(b_pal.begin(), b_pal.end());
  82. 			if (a_pal != "")
  83. 			{				
  84. 				int pos = 1;
  85. 				reverse(a_pal.begin(), a_pal.end());
  86. 				while (pos <= a_pal.length() && ISpal(a_pal.substr(0, pos * 2 + 1)))
  87. 					pos++;
  88. 				a_pal.erase(0, pos);								
  89. 				os += a_pal + pal + b_pal;
  90. 				while (os[cen] == os[cen + 1])
  91. 					os.erase(cen + 1, 1);
  92. 			}
  93. 			else
  94. 			{
  95. 				os += b_pal;
  96. 			}				
  97. 		}
  98. 		cout << os << endl;
  99. 		//puts(&os[0]);
  100. 	}
  101. 	return 0;
  102. }
Success #stdin #stdout 0s 3380KB
comments (?)
stdin
copy 
bcad
bcebccaedbabcbbd
ecacdcae
cde
dbbcedbe
cdeaa
bbabdcabbaaecb
bedcea
aec
edacdbddedbeeca
decbbeeaaedcbcccc
bbabbaeeeaebc
bbaeccbcdbabdeedbc
deaddaaebd
abbbaededbadaeeeecb
bcae
cbcdacebdaecadddd
debeddddbaed
deccbedad
ecaeaaeebec
ecc
edbcdedbdacbaabb
daabebcadbc
ecceabceeadbdbbadea
ebeb
dddaabbeaaebcbcabedc
dceebaccbbdcb
eebeebacadcaedae
ebb
ecccaaaceac
ddaeaebebcaeeeedbaa
c
edabcedbebeeccbebcdd
cdddbddddd
daecbdeabdcead
dcdcbacbadceba
baedcadbcecedec
dabcdebae
caceeeeaedacadbeecdc
deeacabebcbcacdb
ea
bcceab
cedad
babbebcdebaca
abdcccbeacac
aeeeabadcddbaebcbaec
ecdadd
dcedcdcebeaeddadedc
dd
eceedcedcbc
acb
abcebcbbbcaeadabbb
beb
dadba
cec
bebdce
eebcabadadeebaebaa
edddaccccadebdb
deedeccadeacec
acbdddd
badcbd
adaebbdaedebaadd
baeeac
dcbbaab
adbccbebaecceadc
adcaadeeccecaceeddb
d
ccdbddecceabcacbbedb
ddce
bcaededbb
acbeebabeeeadedbede
ccdcbcc
aa
aeabdcebbdadcbcabaec
bccebbacdaecc
bece
ccbbdacb
baaade
bacadeaabaddcdcba
daaacddcdacccbeb
eadeddadcabe
bccecbccbadde
babdeddddcaceaaa
dcccbdeeebeacebccb
caccecedabbeadbcc
edbacbabacabecbdbc
b
ceeceeaebcdebabeaee
ebbdee
cbdaeebdeadacddd
aaddbaddbb
caabbadaaeaeceeeeee
bbdeddebbabbcccecdb
ecd
dcccdccadcbdbdbea
adaaeedaceeabc
abdeadddcdb
aaadbdabceb
d
eedebeceadaddcee
stdout
copy 
bcadacb
bcebccaedbabcbbdbbcbabdeaccbecb
ecacdcaeacdcace
cdedc
dbbcedbebdecbbd
cdeaaedc
bbabdcabbaaecbceaabbacdbabb
bedceaecdeb
aecea
edacdbddedbeecaceebdeddbdcade
decbbeeaaedcbccccbcdeaaeebbced
bbabbaeeeaebcbeaeeeabbabb
bbaeccbcdbabdeedbcbdeedbabdcbcceabb
deaddaaebdbeaaddaed
abbbaededbadaeeeecbceeeeadabdedeabbba
bcaeacb
cbcdacebdaecaddddaceadbecadcbc
debeddddbaedeabddddebed
deccbedadebcced
ecaeaaeebecebeeaaeace
ecce
edbcdedbdacbaabbaabcadbdedcbde
daabebcadbcbdacbebaad
ecceabceeadbdbbadeaedabbdbdaeecbaecce
ebebe
dddaabbeaaebcbcabedcdebacbcbeaaebbaaddd
dceebaccbbdcbcdbbccabeecd
eebeebacadcaedaeadeacdacabeebee
ebbe
ecccaaaceacaecaaaccce
ddaeaebebcaeeeedbaabdeeeeacbebeaeadd
c
edabcedbebeeccbebcddcbebcceebebdecbade
cdddbdddddbdddc
daecbdeabdceadaecdbaedbcead
dcdcbacbadcebabecdabcabcdcd
baedcadbcecedececbdacdeab
dabcdebaeabedcbad
caceeeeaedacadbeecdceebdacadeaeeeecac
deeacabebcbcacdbdcacbcbebacaeed
eae
bcceabaeccb
cedadec
babbebcdebacabedcbebbab
abdcccbeacacaebcccdba
aeeeabadcddbaebcbaeceabcbeabddcdabaeeea
ecdaddadce
dcedcdcebeaeddadedcdedaddeaebecdcdecd
dd
eceedcedcbcdecdeece
acbca
abcebcbbbcaeadabbbadaeacbbbcbecba
beb
dadbabdad
cec
bebdcecdbeb
eebcabadadeebaebaabeabeedadabacbee
edddaccccadebdbedaccccaddde
deedeccadeacecaedaccedeed
acbddddbca
badcbdbcdab
adaebbdaedebaaddaabedeadbbeada
baeeacaeeab
dcbbaabbcd
adbccbebaecceadcdaecceabebccbda
adcaadeeccecaceeddbddeecacecceedaacda
d
ccdbddecceabcacbbedbdebbcacbaecceddbdcc
ddcecdd
bcaededbbdedeacb
acbeebabeeeadedbedebdedaeeebabeebca
ccdcbccbcdcc
aa
aeabdcebbdadcbcabaeceabacbcdadbbecdbaea
bccebbacdaecceadcabbeccb
beceb
ccbbdacbcadbbcc
baaadedaaab
bacadeaabaddcdcbabcdcddabaaedacab
daaacddcdacccbebcccadcddcaaad
eadeddadcabebacdaddedae
bccecbccbaddeddabccbceccb
babdeddddcaceaaaecacddddedbab
dcccbdeeebeacebccbecaebeeedbcccd
caccecedabbeadbccbdaebbadececcac
edbacbabacabecbdbcebacababcabde
b
ceeceeaebcdebabeaeeaebabedcbeaeeceec
ebbdeedbbe
cbdaeebdeadacdddcadaedbeeadbc
aaddbaddbbddabddaa
caabbadaaeaeceeeeeeceaeaadabbaac
bbdeddebbabbcccecdbdcecccbbabbeddedbb
ecdce
dcccdccadcbdbdbeaebdbdbcdaccdcccd
adaaeedaceeabcbaeecadeeaada
abdeadddcdbdcdddaedba
aaadbdabcebecbadbdaaa
d
eedebeceadaddceecddadaecebedee
https://ideone.com/bLEDzL
language:
C++ (gcc 8.3)
created:
9 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!