小易爱回文

Questions:

  小易得到得一个仅包含大小写英文字符的字符串，该字符串可能不是回文串。（“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串，“asds”就不是回文串。）小易可以在字符串尾部加入任意数量的任意字符，使其字符串变成回文串。现在请你编写一个程序，程序要能计算出小易可以得到的最短回文串。

Keys:

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int Miroor(string str)
{
    int begin, end, location=0; //定义起始、末尾和定位的变量
    begin = 0;
    end = str.length() - 1;
    while (begin < end) //循环遍历整个字符串
    {
        //如果找到与末尾相等的字符时，将指向末尾的标号往前移，起始标号往后移，
        //同时位置变量加1，表明回文串目前长度加1（此时为假设的可能回文串）
        if (str[begin] == str[end]) 
        {
            begin++;
            end--;
            location++;
            continue;
        }
        //如果begin指向的当前字符不等于end指向的字符且已有假设的回文串时，
        //说明假设的回文串不成立，end要重回末尾，回文串长度也要置0
        if (location >= 1) 
        {
            location = 0;
            end = str.length() - 1;
        }
        //如果没有与尾部的字符相等，就判断从起始位置开始的下一个字符
        begin++;        
    }
    //循环结束后如果回文串长度为0，说明不存在回文串，从倒数第二个字符开始向前全部复制一遍
    if (location == 0) 
        return str.length() - 1;
    else //若有回文串，则返回回文串的第一个字符的位置
        return begin - location;
}

string Soluton(string str)
{
    if (str.length() <= 0)
        return "";
    if (str.length() == 1)
    {
        str.push_back(str[0]);
        return str;
    }
    int begin = Miroor(str); //获取字符串中存在的回文串的第一个字符位置
    while (begin >= 1)
    {
        str.push_back(str[begin - 1]); //从回文串前一个字符开始，依次将前面的字符复制到尾部
        begin--;
    }
    return str;
}

int main()
{
    string str;
    while (cin >> str) {
        int flag = 0;
        for (int i = 0; i < str.length(); ++i) {
            if (str[i]<'A' || str[i]>'z')
            {
                flag = 1;
                break;
            }
        }
        if (flag == 1)
        {
            cout << "" << endl;
            continue;
        }
        cout << Soluton(str) << endl;
    }
    return 0;
}