题解：UVA353 Pesky Palindromes

题目传送门：

UVA353 Pesky Palindromes (On UVaOJ)

UVA353 Pesky Palindromes (On Luogu)

解题思路

让我们回顾一下题目吧~

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

主要思路：

枚举所有子串：我们需要遍历字符串的所有可能子串。对于一个长度为 $n$ 的字符串，子串的总数是 $O(n^2)$ 级别的。
判断回文：对于每个子串，我们检查它是否为回文。回文的判断方法是：从子串的两端向中间逐个字符比较，如果所有字符都相同，则该子串是回文。
去重：为了避免重复统计相同的回文子串，我们可以使用一个 set 来存储所有找到的回文子串，set 会自动去重。
输出结果：最后，我们输出 set 的大小，即为不同回文子串的数量。

人话：枚举串开头的

i

与结尾的

j

，然后看所构成的字符串是不是回文串，如果是，存入集合中，最后按题目的要求再输出。

AC Code：

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

CPP

#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

题解：UVA353 Pesky Palindromes

文章操作

题解：UVA353 Pesky Palindromes

题目传送门：

解题思路

主要思路：

AC Code：

AC Record：

相关推荐

评论

题解：UVA353 Pesky Palindromes