SPOJ 查找下一个回文Palindrome 算法题解

SPOJ 查找下一个回文Palindrome 算法题解2015-02-25给出一个数值，well，其实不是数值了，而是一大串数字，

比如 98237482340328490328490324893024，非常长的数字。

找出下一个Palindrome，这个Palindrome在数值上要比当前数值大（不能等于）。

如：

9 9 9 9->1 0 0 0 1

1 2 3 4 5 ->1 2 4 2 1

本算法时间效率是O（n），其中n是指数值的位数，不是数值，比如123456789，只有9位，那么本算法接近常数：

#include <iostream>#include <string>using namespace std; bool sPlus1（string &s, int i）{for （; i >= 0 && "9" == s[i]; i--） s[i] = "0";if （i < 0）{s[0] = "1";return true;}else s[i]++;return false;} string nextPalindrom（string &palin）{int l_cen = 0, r_cen = 0;if （palin.size（） % 2） {l_cen = r_cen = （palin.size（）>>1）;}else{r_cen = （palin.size（）>>1）;l_cen = r_cen-1;} int i = l_cen, j = r_cen;for （ ; i >= 0 && j < palin.size（）; i--, j++）{if （palin[i] ！= palin[j]） break;//原来这不是>是！=} bool extra1 = false;if （i >= 0 && palin[j] < palin[i]）{palin[j]++;}elseextra1 = sPlus1（palin, l_cen）; if （extra1）{j = r_cen == l_cen？ r_cen+1 : r_cen;for （; j < palin.size（）; j++） palin[j] = "0";palin.push_back（"1"）;}else{i = l_cen, j = r_cen;for （; j < palin.size（）; i--, j++） palin[j] = palin[i];}return palin;} void TheNextPalindrome（）{string palin;long long T = 0;cin>>T;while （T--）{cin>>palin;cout<<nextPalindrom（palin）<<endl;}}

OJ 参考资料：