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

给出一个数值，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位，那么本算法接近常数：

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

#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]++;
    }
    else    extra1 = 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 参考资料：

http://www.spoj.com/problems/PALIN/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， string
， size
， 数值算法
， else
数值
palindrome 算法、回文数算法、c语言回文数算法、回文算法、java回文数算法，以便于您获取更多的相关知识。