UVa 353 Pesky Palindromes

题目描述回文palindrome\texttt{palindrome}palindrome是指一个或多个字符组成的序列从左向右读和从右向左读相同。例如Z、TOT和MADAM是回文但ADAM不是。你的任务是编写一个程序读取一系列字符串对于每个字符串确定其中不同的回文子串的数量。输入格式输入文件包含多个字符串每行一个每个字符串最多808080个字符从第111列开始。输出格式对于每个非空输入行输出一行格式如样例所示。样例输入boy adam madam tot样例输出The string boy contains 3 palindromes. The string adam contains 4 palindromes. The string madam contains 5 palindromes. The string tot contains 3 palindromes.样例解释boy中的333个不同回文子串b、o、yadam中的444个不同回文子串a、d、m、adamadam中的555个不同回文子串m、a、d、ada、madamtot中的333个不同回文子串t、o、tot题目分析问题的本质这是一个回文子串枚举与去重问题。给定一个字符串需要找出所有不同的回文子串。回文的特点回文有两种类型奇长度回文中心是一个字符左右对称扩展偶长度回文中心是两个相同字符左右对称扩展枚举策略可以枚举每个可能的回文中心向左右扩展收集所有回文子串。时间复杂度O(n2)O(n^2)O(n2)n≤80n \leq 80n≤80完全可行。去重使用setstring自动去重最后输出集合大小。参考代码// Pesky Palindromes// UVa ID: 353// Verdict: Accepted// Submission Date: 2016-06-27// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){string line;while(cinline){setstringpalindromes;// 存储不同的回文子串// 枚举奇长度回文中心为单个字符for(inti0;iline.length();i){intlefti,righti;// 向左右扩展直到不能构成回文while(left0rightline.length()line[left]line[right]){palindromes.insert(line.substr(left,right-left1));left--;right;}}// 枚举偶长度回文中心为两个字符之间的位置for(inti1;iline.length();i){intlefti-1,righti;while(left0rightline.length()line[left]line[right]){palindromes.insert(line.substr(left,right-left1));left--;right;}}coutThe string line contains palindromes.size() palindromes.endl;}return0;}