标签搜索

小易爱回文

爱做梦的月亮
2022-07-22 / 0 评论 / 276 阅读 / 389 个汉字 / 正在检测是否收录...

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;
}
0

评论 (0)

取消