题解：UVA353 Pesky Palindromes

· · 题解

题解：UVA353 Pesky Palindromes

题目传送门：

UVA353 Pesky Palindromes (On UVaOJ)

UVA353 Pesky Palindromes (On Luogu)

解题思路

让我们回顾一下题目吧~

这道题要求我们统计一个字符串中不同的回文子串的数量。回文子串是指从左到右和从右到左读都相同的子串。我们需要遍历字符串的所有可能子串，并判断其是否为回文，同时确保这些回文子串是唯一的。

主要思路：

  1. 枚举所有子串：我们需要遍历字符串的所有可能子串。对于一个长度为 n 的字符串，子串的总数是 O(n^2) 级别的。

  2. 判断回文：对于每个子串，我们检查它是否为回文。回文的判断方法是：从子串的两端向中间逐个字符比较，如果所有字符都相同，则该子串是回文。

  3. 去重：为了避免重复统计相同的回文子串，我们可以使用一个 set 来存储所有找到的回文子串，set 会自动去重。

  4. 输出结果：最后，我们输出 set 的大小，即为不同回文子串的数量。

人话：枚举串开头的 i 与结尾的 j ，然后看所构成的字符串是不是回文串，如果是，存入集合中，最后按题目的要求再输出。

AC Code：

// 抄题解的代码只能增加估值，不能提升自己，不要抄题解！一定要能理解

#include<iostream>
#include<set>
#include<string>
#define Luogu using
#define Article namespace
#define HuangRuibo std
Luogu Article HuangRuibo;
bool HUIWEN(const string& s)//不会英文的屑...
{
    int left=0,right=s.size()-1;//从i(left)到j(right)枚举 
    while(left<right)
    {
        if(s[left]!=s[right])
        {
            return false;
        }
        left++;//缩小范围 
        right--;//同上 
    }
    return true;
}

int main()
{
    string str;
    while(cin>>str)//while直到没有输入了 
    {
        set<string> huiwen;//屑 
        int n=str.size();

        for(int i=0;i<n;++i)
        {
            for(int j=i;j<n;++j)
            {
                string _substr_=str.substr(i,j-i+1);
                if(HUIWEN(_substr_))
                {
                    huiwen.insert(_substr_);
                }
            }
        }

        cout<<"The string '"<<str<<"' contains "<<huiwen.size()/*"huiwen"的大小*/<<" palindromes."<<endl;//按要求输出(小心别写错了awa)
    }
    return 0;//完结撒花！！
}

AC Record：

Luogu(洛谷上咋都UKE了？)

UVa