CF1304B Longest Palindrome(可逆转符号,数学分析,回文串)

简介: CF1304B Longest Palindrome(可逆转符号,数学分析,回文串)

题目描述



Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse. For example, strings "pop", "noon", "x", and "kkkkkk" are palindromes, while strings "moon", "tv", and "abab" are not. An empty string is also a palindrome.


Gildong loves this concept so much, so he wants to play with it. He has nn distinct strings of equal length mm . He wants to discard some of the strings (possibly none or all) and reorder the remaining strings so that the concatenation becomes a palindrome. He also wants the palindrome to be as long as possible. Please help him find one.


输入格式



The first line contains two integers nn and mm ( 1 \le n \le 1001≤n≤100 , 1 \le m \le 501≤m≤50 ) — the number of strings and the length of each string.


Next nn lines contain a string of length mm each, consisting of lowercase Latin letters only. All strings are distinct.


输出格式



In the first line, print the length of the longest palindrome string you made.


In the second line, print that palindrome. If there are multiple answers, print any one of them. If the palindrome is empty, print an empty line or don't print this line at all.


题意翻译



  • 给你  n 个长度为  m 的字符串。
  • 请你判断删去其中的几个(或者不删去),能使得将剩下字符串随意排列所形成的回文串长度最大。
  • 请你输出最大的长度和那个回文串。
  • 1≤n≤100, 1≤m≤50。


输入输出样例



输入  

3 3

tab

one

bat


输出  

6

tabbat


输入

4 2

oo

ox

xo

xx


输出  

6

oxxxxo


输入

3 5

hello

codef

orces


输出  

0


输入

9 4

abab

baba

abcd

bcde

cdef

defg

wxyz

zyxw

ijji


输出  

20

ababwxyzijjizyxwbaba


题目刨析,首先我们观察答案发现是由2*n个互相可以颠倒相同的字符串组成,或者由2*n个互相颠倒的字符串组成然后再字符串中间加上一个本身可以颠倒的字符串组成答案,所以我们思路是定一个字符串然后遍历后面的字符串,如果相同用一个string来存字符串,最后找一个自身颠倒自己的字符串加在中间,退出循环。就是答案。思路就是这样,具体操作看代码。


#include<bits/stdc++.h>
using namespace std;
struct node{
  string word;//字符串
  int flag;//标记是否已经用过、、先默认为·0 
}a[105];
string ans;//用来输出
int main()
{
  int n,m;
  cin>>n>>m;
  getchar();
  for(int i=0;i<n;i++)
      cin>>a[i].word;
   for(int i=0;i<n;i++)
        {
      if(!a[i].flag)//=0
      { 
         for(int j=i+1;j<n;j++)//枚举i后面字符串是否对称
        {
          string temp=a[j].word;
          reverse(temp.begin(),temp.end());//反转字符串 
            if(strcmp(a[i].word.c_str(),temp.c_str())==0)//第一个是前面的反转后的字符,第二个是后面的字符看是不是相等 
            {
              ans=a[i].word+ans+a[j].word;//string 可以直接连在一起 
              a[i].flag=a[j].flag=1;//标记 
            }
        }
          } 
      }
    for(int i=0;i<n;i++)
    {
        if(!a[i].flag)//=0
        {
          string temp=a[i].word;
          reverse(temp.begin(),temp.end());
          if(strcmp(temp.c_str(),a[i].word.c_str())==0)//看自己是不是回文串 
          {
             ans.insert(ans.size()/2,a[i].word);//插入自身对称的字符串(回文串)
                break;
          }
            }
    }
    cout<<ans.size()<<"\n";
    cout<<ans<<endl;
 } 
相关文章
|
8月前
|
测试技术
最大连续子序列 (HDU - 1231)
最大连续子序列 (HDU - 1231)
|
8月前
LeetCode题 338比特位计数,20有效的括号,415字符串相加
LeetCode题 338比特位计数,20有效的括号,415字符串相加
72 0
|
8月前
分解质因数答疑 为什么只需要枚举到根号N 为什么n % i == 0就是质数
分解质因数答疑 为什么只需要枚举到根号N 为什么n % i == 0就是质数
71 0
|
存储 算法
【LeetCode】每日一题&最后一个单词的长度&投票法求解多数元素&异或操作符巧解只出现一次的数字&整数反转
【LeetCode】每日一题&最后一个单词的长度&投票法求解多数元素&异或操作符巧解只出现一次的数字&整数反转
华为机试HJ1:字符串最后一个单词的长度
华为机试HJ1:字符串最后一个单词的长度
|
算法 C++
C++/PTA 最长对称子串
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。
92 0
Leetcode-每日一题777. 在LR字符串中交换相邻字符
在去掉所有X的两个字符串序列不相等,则他们永远不可能通过操作变成相同,例如:start:LXR,end:RXL,不管你怎么移动都不可能使两个字符串相同。
108 0
Leetcode-每日一题777. 在LR字符串中交换相邻字符
PTA 7-5 子串与子列 (25 分)
子串是一个字符串中连续的一部分,而子列是字符串中保持字符顺序的一个子集,可以连续也可以不连续。
180 0
LeetCode每日一题——777. 在LR字符串中交换相邻字符
在一个由 ‘L’ , ‘R’ 和 ‘X’ 三个字符组成的字符串(例如"RXXLRXRXL")中进行移动操作。一次移动操作指用一个"LX"替换一个"XL",或者用一个"XR"替换一个"RX"。
99 0
|
算法
LeetCode算法:求出字符串的最大回文子串 及 长度【只利用字符串反转就可】
LeetCode算法:求出字符串的最大回文子串 及 长度【只利用字符串反转就可】
91 0