fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int location, temp_max;
  7. int KMP(string S, string K){
  8. 	vector<int> T(K.size()+1, -1);
  9.  
  10. 	//prepare partial match table
  11. 	for(int i = 1; i <= K.size(); i++){
  12. 		int pos = T[i-1];
  13. 		while(pos != -1 && K[pos] != K[i-1]) pos = T[pos];
  14. 		T[i] = pos + 1;
  15. 	}
  16.  
  17. 	int sp = 0, kp = 0,temp = 0;
  18. 	temp_max = 0, location = 0;
  19.  
  20. 	//actual KMP algorithm
  21. 	while(sp < S.size()){
  22. 		while(kp != -1 && (kp == K.size() || K[kp] != S[sp])) kp = T[kp];
  23. 		kp++;
  24. 		sp++;
  25. 		temp = kp; 
  26. 		if(temp > temp_max){ location = sp-temp_max-1; temp_max = temp; }//cout << location<<","<<temp_max<<"\t";}
  27. 	}
  28. 	//location = S.size()-temp_max ;
  29. 	//cout<<"location = "<<location<<"\n";
  30. 	return location;
  31. }
  32.  
  33. int main() {
  34. 	// your code goes here
  35. 	string s, rev_s;
  36. 	int x,temporary;
  37. 	while(!cin.eof()){
  38. 		cin >> s;
  39. 		string right,left,temp1,temp2;
  40. 		rev_s.resize(s.size());
  41. 		reverse_copy(s.begin(), s.end(), rev_s.begin());
  42. 		//cout<<s<<endl;
  43. 		//cout<<rev_s<<endl;
  44. 		x = 0;
  45. 		x = KMP(s, rev_s);
  46. 		if(x == s.size()){
  47. 			cout<<s<<endl;
  48. 		}
  49. 		else{
  50. 			//cout << location << "\t" << temp_max <<"\t"<<s.size() <<"\n";
  51. 			temporary = s.size();
  52. 			left.resize(temporary);
  53. 			right.resize(temporary);
  54. 			temp1.resize(temporary);
  55. 			temp2.resize(temporary);
  56. 			if(location+temp_max < temporary){
  57. 				if(location == 0)
  58. 				{
  59. 					reverse_copy(s.begin(),s.end()-temp_max,right.begin());	
  60. 					cout<<s<<right<<"\n";
  61. 				}
  62. 				else if(location != 0)
  63. 				{
  64. 					reverse_copy(s.begin()+location,s.begin()+location+temp_max,temp1.begin());
  65. 					copy(s.begin()+location,s.begin()+location+temp_max,temp2.begin());
  66. 					if(equal(temp1.begin(),temp1.end(),temp2.begin()))
  67. 					{
  68. 						//if end part is palindrome itself
  69. 						//cout<<temp1<<"\t"<<temp2<<"\n";
  70. 						//cout<<"working";
  71. 						reverse_copy(s.begin(),s.end()-temp_max,right.begin());
  72. 						cout<<s<<right<<"\n";
  73. 					}
  74. 					else
  75. 					{
  76. 						reverse_copy(s.begin(),s.end()-1,right.begin());
  77. 						cout<<s<<right<<"\n";
  78. 					}
  79. 				}
  80. 			}
  81. 			else
  82. 			{
  83. 				s.resize(s.size()+x);
  84. 				reverse_copy(s.begin(),s.begin()+x, s.begin()+temporary);
  85. 				cout<<s<<"\n";
  86. 			}
  87. 		}
  88. 	}
  89. 	return 0;
  90. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
aaabcdxxxx
abcdefglananahijklmnopqrstananal
laxalghijklaxal
aaaalaa
jklaxalghijklaxal
jkaaaajkaaaahijkaaaa
abcdlaxaxalaxaxaxaxa
stdout
copy 
aaabcdxxxxdcbaaa
abcdefglananahijklmnopqrstananalananatsrqponmlkjihananalgfedcba
laxalghijklaxalkjihglaxal
aaaalaaaa
jklaxalghijklaxalkjihglaxalkj
jkaaaajkaaaahijkaaaakjihaaaakjaaaakj
abcdlaxaxalaxaxaxaxalaxaxaldcba
https://ideone.com/ykWbaR
SPOJ EPALIN
language:
C++ (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!