fork(1) download
copy 
  1. /**
  2.  * Calculate the minimal number of letters one should add to a given string to make it a palindrome.
  3.  * INPUT:
  4.  *   A string.
  5.  * OUTPUT:
  6.  *   The minimal number of letters we should insert to the string to make it a palindrome.
  7.  * ALGORITHM: 
  8.  *   - Loop over all characters s[i].
  9.  *   - Assume that s[i] is the center of the palindrome.
  10.  *      - (if s[i]==s[i+1], assume that s[i,i+1] are the center).
  11.  *   - Calculate the edit distance between the two sides of s[i].
  12.  *   - Return the minimum edit distance.
  13.  *
  14.  * @author Erel Segal
  15.  * @date 2010-11-02
  16.  */
  17.  
  18. #include <iostream>
  19. #include <vector>
  20. #include <algorithm>
  21. #include <assert.h>
  22. using namespace std;
  23.  
  24.  
  25. template <class T> class matrix {
  26. protected:
  27.   uint myRows, myCols;
  28.   vector<T> myData;
  29. public:
  30.   matrix<T> () {}
  31.   matrix<T> (uint rows, uint cols): 
  32.     myRows(rows), myCols(cols),
  33.     myData(rows*cols) {} 
  34.  
  35.   void resize (int rows, int cols) {
  36.     myRows=rows; myCols=cols;
  37.     myData.resize(rows*cols);
  38.   }
  39.  
  40.   T& at(uint row, uint col) { return myData[row*myCols+col]; }
  41.   const T& at(uint row, uint col) const { return myData[row*myCols+col]; }
  42.  
  43.   void fill (T value) { ::fill(myData.begin(), myData.end(), value); }
  44.  
  45.   void print(ostream& out) const {
  46.     for (uint row=0; row<myRows; ++row) {
  47.       const T* temp = &myData[row*myCols];
  48.       for (uint col=0; col<myCols; ++col) {
  49.         out << temp[col] << " ";
  50.       }
  51.       out << endl;
  52.     }
  53.   }
  54.  
  55.   friend ostream& operator<< (ostream& out, const matrix<T>& m) { m.print(out); return out; }
  56. };
  57.  
  58. /** Compute the longest common subsequence between X and Y
  59.  * On return, C will contain the LCS table.
  60.  * @return C[m][n], that is the length of the longest common subsequence.
  61.  * @see http://e...content-available-to-author-only...s.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence#C.2B.2B
  62.  * @see http://e...content-available-to-author-only...a.org/wiki/Longest_common_subsequence_problem#Relation_to_other_problems
  63.  */
  64. template<typename Iterator> size_t editDistance(Iterator X, Iterator Xend, Iterator Y, Iterator Yend) {
  65. 	size_t m = std::distance(X, Xend);
  66. 	size_t n = std::distance(Y, Yend);
  67. 	matrix<size_t> C(m+1, n+1);
  68.  
  69. 	// Initialize the zeroth row and zeroth column:
  70. 	for (size_t i=0; i<=m; ++i)
  71. 	  C.at(i,0) = 0;
  72. 	for (size_t j=0; j<=n; ++j)
  73. 	  C.at(0,j) = 0;
  74.  
  75. 	for (size_t i=0; i<m; ++i)
  76. 	  for (size_t j=0; j<n; ++j)
  77. 	    if (X[i] == Y[j])
  78. 	      C.at(i+1,j+1) = C.at(i,j) + 1;
  79. 	    else
  80. 	      C.at(i+1,j+1) = std::max(C.at(i+1,j), C.at(i,j+1));
  81.  
  82. 	size_t LCSLength = C.at(m,n);
  83. 	return m+n-2*LCSLength;
  84. }
  85.  
  86.  
  87. void minimizePalindromizationCost(size_t& minimumCost, const string& forward, const string& backward, size_t length, size_t centerPosition) {
  88. 		//cout << "center=" << centerPosition << " ";
  89. 		if (centerPosition>=length)
  90. 			return;
  91. 		if (centerPosition>0 && forward[centerPosition]==forward[centerPosition-1])
  92. 			return; // a substring of identical letters is checked when it starts.
  93.  
  94. 		char centerLetter = forward[centerPosition];
  95. 		size_t centerLength=1;  // The number of letters identical to centerLetter
  96. 		++centerPosition;
  97. 		while (centerPosition<length && forward[centerPosition]==centerLetter) {
  98. 			++centerLength;
  99. 			++centerPosition;
  100. 		}
  101. 		//cout << centerPosition << ":" << centerLength << ":";
  102.  
  103. 		size_t lengthForward = centerPosition-centerLength;
  104. 		size_t lengthBackward = length-centerPosition;
  105. 		if ((size_t)abs((int)lengthForward-(int)lengthBackward)>=minimumCost)
  106. 			return; // the edit distance cannot be smaller!
  107.  
  108. 		size_t currentCost = editDistance(
  109. 			forward.begin(), forward.begin()+lengthForward,
  110. 			backward.begin(), backward.begin()+lengthBackward);
  111. 		//cout << currentCost << endl;
  112.  
  113. 		if (currentCost<minimumCost)
  114. 			minimumCost = currentCost;
  115. }
  116.  
  117.  
  118. size_t palindromizationCost(const string& forward) {
  119. 	size_t length = forward.size();
  120. 	size_t middle = length/2; // TODO: start with the middle to save cost
  121.  
  122. 	string backward=forward;
  123. 	reverse(backward.begin(), backward.end());
  124.  
  125. 	size_t minimumCost = length-1;
  126. 	size_t centerPosition;
  127. 	for (size_t radius=0; radius<=length/2; ++radius) {
  128. 		//cout << "radius=" << radius << " ";
  129. 		centerPosition = middle+radius;
  130. 		if (centerPosition<length) 
  131. 			minimizePalindromizationCost(minimumCost, forward, backward, length, centerPosition);
  132. 		if (radius==0) continue; // check the other direction only when radius>0
  133. 		centerPosition = middle-radius;
  134. 		minimizePalindromizationCost(minimumCost, forward, backward, length, centerPosition);
  135. 	}
  136.  
  137. 	return minimumCost;
  138. }
  139.  
  140. void assertCost(string s, size_t expected) {
  141. 	time_t before = time(NULL);
  142. 	size_t a = palindromizationCost(s);
  143. 	if (a!=expected) {
  144. 		cerr << "ERROR: Cost of " << s << " should be " << expected << " but was " << a << endl;
  145. 	} else {
  146. 		time_t after = time(NULL);
  147. 		cout << "calculated cost of " << s.size() << " chars in " << (after-before) << " seconds" << endl;
  148. 	}
  149. }
  150.  
  151. void testIdentical(int N) {
  152. 	string s(N, 'b');
  153. 	assertCost(s,0);
  154. }
  155.  
  156. void testHalf(int N) {
  157. 	N += (N%2); // make N even
  158. 	string s(N, 'b');
  159. 	for (int i=0; i<N/2; ++i) {
  160. 		s[i] = 'a';
  161. 	}
  162. 	assertCost(s,N/2);
  163. }
  164.  
  165. void testAlternating(int N) {
  166. 	N += (N%2); // make N even
  167. 	string s(N, 'b');
  168. 	for (int i=0; i<N; i+=2) {
  169. 		s[i] = 'a';
  170. 	}
  171. 	assertCost(s,1);
  172. }
  173.  
  174. void testStart(int N) {
  175. 	string s(N, 'b');
  176. 	s[0] = 'a';
  177. 	assertCost(s,N>1? 1: 0);
  178. }
  179.  
  180. void testStartEnd(int N) {
  181. 	string s(N, 'b');
  182. 	s[0] = 'a';
  183. 	s[N-1] = 'c';
  184. 	assertCost(s, N>2? 2: N==2? 1: 0);
  185. }
  186.  
  187. void testStartEndIdentical(int N) {
  188. 	string s(N, 'b');
  189. 	s[0] = 'a';
  190. 	s[N-1] = 'a';
  191. 	assertCost(s,0);
  192. }
  193.  
  194. void testDifferent(int N) {
  195. 	string s(N, 'a');
  196. 	for (int i=0; i<N; i++) {
  197. 		s[i] = (i%256);
  198. 	}
  199. 	assertCost(s,N-1);
  200. }
  201.  
  202.  
  203.  
  204. int main() {
  205. 	size_t N;
  206. 	cin >> N; // length of string
  207.  
  208. 	/* tests: 
  209. 	assertCost("Ab3bd",2);
  210. 	testIdentical(N);
  211. 	testHalf(N);
  212. 	testAlternating(N);
  213. 	testStart(N);
  214. 	testStartEnd(N);
  215. 	testStartEndIdentical(N);
  216. 	testDifferent(N);
  217. 	*/
  218.  
  219. 	string s;
  220. 	cin >> s;
  221.  
  222. 	cout << palindromizationCost(s) << endl;
  223. }
  224.  
Success #stdin #stdout 0s 2868KB
comments (?)
stdin
copy 
5
Ab3bd
stdout
copy 
2
https://ideone.com/Y9g67
language:
C++ (gcc 8.3)
created:
13 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!