京京和东东是好朋友。东东很喜欢回文。回文是指从前往后读和从后往前读是一样的词语。京京准备给东东一个惊喜,先取定一个字符串s,然后在后面附上 0 个或者更多个字母形成回文,京京希望这个回文越短越好。请帮助京京计算他能够得到的最短的回文长度。
数据范围：输入的字符串长度满足 
，且保证只含有小写英文字母
[编程题]回文
import java.util.*;
public class Main {
private static final int MAX = 50+5;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] arr = sc.next().toCharArray();
int n = arr.length;
for (int i=0; i!=n; i++) {
if (judgePlalindrome(arr, i, n-1)) {
System.out.println(n+i);
return;
}
}
return;
}
private static boolean judgePlalindrome(char[]a, int i, int j) {
while (i <= j) {
if (a[i++] != a[j--]) { return false; }
}
return true;
}
}
发表于 2019-01-27 18:00:15
回复(2)
找寻规律，从i=0开始判断这个改字符到最后一个字符是否是回文串，如果是，字符串长度加上i就是最终结果。
import java.util.Scanner;
public class Main {
public static boolean isPalindrome(char[] ch, int i, int j) {
while (i < j) {
if (ch[i++] != ch[j--]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] ch = sc.next().toCharArray();
for (int i = 0; i < ch.length; i++) {
if (isPalindrome(ch, i, ch.length - 1)) {
System.out.println(ch.length + i);
break;
}
}
}
}
发表于 2019-06-14 16:29:33
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
bool huiwen(string s)
{ string s2 = s; reverse(s2.begin(),s2.end()); if (s2 == s) return true; else return false;
}
int main()
{ string s; cin >> s;
if(huiwen(s))//如果s本身就是回文就不需要再添加字母，直接输出s的长度就行
{
cout<<s.size()<<endl;
}
else
{
int i=0;
for (i = 1; i < s.size(); ++i) {
string tmp = s;
string tmp1 = tmp.substr(0,i);
reverse(tmp1.begin(), tmp1.end());
tmp = tmp +tmp1 ;
if (huiwen(tmp) == true)
{
cout << tmp.size() << endl;
break;
} }
} return 0;
}
发表于 2019-05-07 11:52:52
回复(0)
//只能在末尾进行添加
#include <string>
#include <iostream>
using namespace std;
bool judge(string word){
int lo=0,hi=(int)word.length()-1;
while(lo<=hi)
if(word[lo++]!=word[hi--])
return false;
return true;
}
int main(){
string s;
cin>>s;
if(judge(s)){ //如果自身就是一个回文串
cout<<(int)s.length();
return 0;
}
//否则在尾部进行添加
int i;
for(i=1;i<(int)s.length();++i){
if(s[i]==s.back()){ //找第一个可能的最小情况
if(judge(s.substr(i))){ //如果当前区间内已经是回文，添加i之前的字符即可
cout<<(int)s.length()+i;
return 0;
}
}
}
cout<<2*(int)s.length();
return 0;
}
发表于 2019-02-22 10:57:48
回复(0)
这个题是往原字符串的后面添加字符，因此我们只需要考虑从后面截取原字符串能截取的最长回文串有多长。例如：
(1) abacaba，这个字符串本来就是回文串，因此能截取的最长回文串长度为7；
(2) abab，这个字符串从后面能截取的最长回文串为bab（原字符串从下标1开始的后面部分），因此能截取的最长回文串长度为3，只需要在后面添加一个a就能够构成回文串ababa，长度为1+4=5。
根据以上思路不难发现规律：记原字符串为s，我们从下标start=0开始截取后面的子串，如果子串s.substrings(start,s.length())是回文串，那我们在后面添加字符后得到的最短回文串长度应该为start+s.length()。而回文串的判定我们可以采用双指针法。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine().trim();
int n = str.length();
int start = 0;
while(start < n){
if(isPalindrome(str.substring(start, n))) break;
start ++;
}
System.out.println(start + n);
}
private static boolean isPalindrome(String str){
int left = 0, right = str.length() - 1;
while(left < right){
if(str.charAt(left) != str.charAt(right))
return false;
else{
left ++;
right --;
}
}
return true;
}
}
发表于 2021-02-23 10:20:28
回复(0)
python多行
//最能向后追加的最小长度回文字符串 mystr = input() n = len(mystr) if n==1: print(1) else: allflag = True //全部相同 obj = mystr[0] dp = [2*n-1]*n for index in range(1,n): if obj != mystr[index]: allflag = False if index < n - index - 1: continue else: flag1 = flag2 = True //奇偶 for i in range(index+1,n): if mystr[i]!=mystr[index-(i-index)]: flag1 = False if mystr[i]!=mystr[index-(i-index)+1]: flag2 = False mymin = 2*n-1 if flag1 and 2*index+1 <mymin: mymin = 2*index+1 if flag2 and 2*(index+1)<mymin: mymin = 2*(index+1) dp[index] = mymin if allflag: print(n) else: print(min(dp))
编辑于 2019-04-13 14:52:03
回复(0)
以abab为例，你在后面添加a，由于a和a是回文的，你只要判断bab是否回文？
同理，以abcc为例，你在后面添加ba，ba和ab是回文的，你只要判断cc是否回文？
所以在 一个任意字符串 s; 你在后面添加i个字符，由于前i个字符和后面i个字符是回文的，你只要判断从i位置起，长度为s.s.length()-i 的子串是否回文。
#include<iostream>
#include<string>using namespace std;
int fun(string a);
int main()
{
string s;
cin>>s;
int len=s.length();
int num=0;//需要添加的字母数
for (int i=0;i<=len-1;i++)
{
if(fun(s.substr(i,len-i)))//判断字符串是否为回文，若不是继续判断其位置i以后的len-i个字符的字串是否回文。
break;
num++;
}
cout<<num+len;
return 0;
}
//判断是否回文
int fun(string a)
{
int len=a.length();
if(len==1)
return 1;
for (int i=0;i<=len/2;i++)
{
if(a[i]!=a[len-i-1])
return 0;
}
发表于 2019-03-17 17:06:49
回复(5)
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
string s;
cin >> s;
int strSize = s.size();
if(strSize == 1){
cout << 1 << endl;
return 0;
}
while(strSize < 2 * s.size() - 1){
if(strSize % 2 == 0){
//偶数
int m = strSize / 2;
int n = m - 1;
while(n >= 0 && m < s.size()){
if(s[n] == s[m]){
if(n == 0 || m == s.size() - 1){
cout << strSize << endl;
return 0;
}
n--;
m++;
}
else{
break;
}
}
strSize++;
}
else{
//不为1的奇数
int m = strSize / 2 + 1;
int n = strSize / 2 - 1;
while(n >= 0 && m < s.size()){
if(s[n] == s[m]){
if(n == 0 || m == s.size() - 1){
cout << strSize << endl;
return 0;
}
n--;
m++;
}
else{
break;
}
}
strSize++;
}
}
cout << strSize << endl;
return 0;
}
发表于 2019-02-25 22:16:49
回复(0)
#include<iostream>
using namespace std;
bool isPalindrome(string s){
int start = 0;
int end = s.size()-1;
while(start<end){
if(s[start]!=s[end])
return false;
start++,end--;
}
return true;
}
int main(){
string s;
while(cin >> s){
int n = s.size();
int maxPali = 1;
for(int i=0;i<n;i++){
if(isPalindrome(s.substr(i,n))){
maxPali = n-i;
break;
}
}
int res = 2*n-maxPali;
cout << res << endl;
}
return 0;
}
using namespace std;
bool isPalindrome(string s){
int start = 0;
int end = s.size()-1;
while(start<end){
if(s[start]!=s[end])
return false;
start++,end--;
}
return true;
}
int main(){
string s;
while(cin >> s){
int n = s.size();
int maxPali = 1;
for(int i=0;i<n;i++){
if(isPalindrome(s.substr(i,n))){
maxPali = n-i;
break;
}
}
int res = 2*n-maxPali;
cout << res << endl;
}
return 0;
}
发表于 2018-06-02 10:26:09
回复(0)
#include<iostream>
#include<sstream>
using namespace std;
bool Palindrome(string& str,int cur_idx)
{
int sz = str.size()- cur_idx;
for(int i=0;i<sz/2;++i)
{
if(str[i+cur_idx]!=str[cur_idx+sz-i-1])
{
return false;
}
}
return true;
}
int main()
{
string str;
while(cin>>str)
{
int sz_origin = str.size();
int i=0;
// 判断[i,sz_origin]之间的字符是不是回文
// 最后的结果为 i+sz_origin
while(!Palindrome(str,i))
{
++i;
}
cout<<i+sz_origin<<endl;
}
return 0;
}
发表于 2021-04-09 09:11:16
回复(0)
input_s = input()
def findHuiwen(input_s):
start_idx = len(input_s) //2
# even_flag == len(input_s)%2
end = len(input_s)
huiwen_length = 0
for idx in range(start_idx, end):
odd_count = even_count = 0
for i in range(0,end-idx):
# 比较偶数，
if input_s[idx+i] == input_s[idx-i-1]:
even_count +=1
# 比较奇数
if input_s[idx+i] == input_s[idx-i]:
odd_count +=1
if even_count == end - idx:
huiwen_length = idx*2
break
if odd_count == end - idx:
huiwen_length = idx*2 + 1
break
print(huiwen_length)
def findHuiwen(input_s):
start_idx = len(input_s) //2
# even_flag == len(input_s)%2
end = len(input_s)
huiwen_length = 0
for idx in range(start_idx, end):
odd_count = even_count = 0
for i in range(0,end-idx):
# 比较偶数，
if input_s[idx+i] == input_s[idx-i-1]:
even_count +=1
# 比较奇数
if input_s[idx+i] == input_s[idx-i]:
odd_count +=1
if even_count == end - idx:
huiwen_length = idx*2
break
if odd_count == end - idx:
huiwen_length = idx*2 + 1
break
print(huiwen_length)
findHuiwen(input_s)
第一层循环从中间开始查找，查询到输入字符串的长度，第二层循环同时逐步比较奇数和偶数，只要有一个条件满足，就可以由当前的idx得到回文长度。
发表于 2020-07-21 09:54:27
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
String s = new Scanner(System.in).nextLine();
for(int i=0;i<s.length();++i){
if(check(s.substring(i))){
System.out.println(i+s.length());
break;
}
}
}
public static boolean check(String x){
StringBuffer sb = new StringBuffer(x);
return x.equals(sb.reverse().toString());
}
}
编辑于 2020-07-05 15:08:30
回复(0)
首先可以写一个判断是否是回文的函数，然后设想，如果本身并不是回文字符串，需要通过添加字母实现回文的话，最好的情况是添加一个字符实现回文，那么这个字符就等于字符串的首字符；如果只需要添加两个字符的话，那么添加的就是字符串的前面的两个字符......这里面隐含的就是：无论额外添加了几个字符，那么这几个字符是与字符串前面相应的字符对应，那么相应删掉前面相应的字符，使剩余字符串为一个回文即可，输出删掉的字符数num，也即添加的字符数，输出（num+原字符串长度）
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace New_journey
{
class Program
{
static void Main(string[] args)
{
string s1 =null;
while (!string.IsNullOrEmpty(s1 = Console.ReadLine()))
{
int num = s1.Length;
for(int i = 0; i < num; i++)
{
if (ishuiwen(s1))
{
Console.WriteLine(i + num);
break;
}
else
{
s1 = s1.Substring(1);
}
}
}
}
static bool ishuiwen(string s)
{
int len = s.Length;
for (int i = 0; i <= len / 2; i++)
{
if (s[i] != s[len - 1 - i])
{
return false;
}
}
return true;
}
}
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace New_journey
{
class Program
{
static void Main(string[] args)
{
string s1 =null;
while (!string.IsNullOrEmpty(s1 = Console.ReadLine()))
{
int num = s1.Length;
for(int i = 0; i < num; i++)
{
if (ishuiwen(s1))
{
Console.WriteLine(i + num);
break;
}
else
{
s1 = s1.Substring(1);
}
}
}
}
static bool ishuiwen(string s)
{
int len = s.Length;
for (int i = 0; i <= len / 2; i++)
{
if (s[i] != s[len - 1 - i])
{
return false;
}
}
return true;
}
}
}
发表于 2020-05-13 20:08:02
回复(0)
从加0个字母到加strlen(s)-1个字母暴力枚举就行了
#include <stdio.h>
#include <string.h>
char s[60];
int main()
{
int i,j,k,len,flag;
gets(s);
len = strlen(s);
for(i=0;i<len;i++)
{
flag = 1;
char ss[60]={0};
for(j=0;j<len;j++)
ss[j] = s[j];
for(k=i-1;k>=0;k--)
ss[j++] = s[k];
for(j--,k=0;j>=k;j--,k++)
if(ss[j]!=ss[k])
{
flag = 0;
break;
}
if(flag)
{
printf("%d\n",len+i);
return 0;
}
}
return 0;
}
发表于 2019-08-22 10:42:22
回复(0)
//我说怎么似曾相识，又写了一遍
import java.util.*;
public class Main{
public static void main(String[] arg){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
Cal(sc);
}
}
public static void Cal(Scanner sc){
String s=sc.next();
int i=0;
for(i=0;i<s.length();i++){
String t=s.substring(i);
if(PanDu(t)) break;
}
System.out.println(s.length()+i);
}
public static boolean PanDu(String s){
StringBuffer t=new StringBuffer(s);
t.reverse();
if(s.equals(t.toString())) return true;
else return false;
}
}
//*********************************************************************
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
CAL(sc);
}
}
public static void CAL(Scanner sc){
String s=sc.next();
String c="";
{
int i=0;
for (i=0;i<s.length()-1;i++){
c=c+s.charAt(i);
c=c+'*';
}
c=c+s.charAt(i);
}
int j=0;
for(int i=c.length()/2;i<c.length();i++,j=j+2){
if (PanDu(c.substring(j,i),c.substring(i+1))){
break;
}
}
System.out.println(j/2+s.length());
}
public static boolean PanDu(String s1,String s2){ StringBuffer cBuffer2=new StringBuffer(s2); s2=cBuffer2.reverse().toString();
return s1.equals(s2);
}
编辑于 2019-07-06 16:16:43
回复(0)
//与尾部相等就检查是否构成回文，不构成继续往下->最好O（n）最慢O（n2）
#include<iostream>
#include<string>
using namespace std;
int main(){
string s;cin>>s;
size_t n=s.size();
for(size_t i=0;i!=n;++i){
if(s[i]!=s[n-1]){
s.insert(s.begin()+n,s[i]);
}
else{
int left=i+1,right=n-2;bool hw=true;
while(left<right){
if(s[left]!=s[right]) {hw=false;break;}
++left;--right;
}
if(hw) break;
else{
s.insert(s.begin()+n,s[i]);
}
}
}
cout<<s.size()<<endl;
return 0;
}
#include<string>
using namespace std;
int main(){
string s;cin>>s;
size_t n=s.size();
for(size_t i=0;i!=n;++i){
if(s[i]!=s[n-1]){
s.insert(s.begin()+n,s[i]);
}
else{
int left=i+1,right=n-2;bool hw=true;
while(left<right){
if(s[left]!=s[right]) {hw=false;break;}
++left;--right;
}
if(hw) break;
else{
s.insert(s.begin()+n,s[i]);
}
}
}
cout<<s.size()<<endl;
return 0;
}
发表于 2019-06-10 11:01:29
回复(0)
用马拉松算法，限制回文条件为：回文串一定要包含最后一个字符即可
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string mk_new(string s) {
string s_new;
s_new = "";
s_new = s_new + "$#";
for (int i = 0; i < s.length(); i++) {
s_new = s_new + s[i];
s_new = s_new + '#';
}
s_new = s_new + '\0';
return s_new;
}
int main() {
string s,s_new;
cin >> s;
s_new = mk_new(s);
int id = 0;
int mx = 0;
int Max_len = -1;
vector<int> P(s_new.length());
for (int i = 1; i < s_new.length(); i++) {
if (i < mx) {
P[i] = min(P[2 * id - i], mx - i);
}
else {
P[i] = 1;
}
while (s_new[i - P[i]] == s_new[i + P[i]]) {
P[i]++;
}
if (mx < i + P[i]) {
mx = i + P[i];
id = i;
}
if (mx == s_new.length() - 1) {
Max_len = P[i] - 1;
break;
}
}
cout<< 2*s.length() -Max_len;
return 0;
}
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string mk_new(string s) {
string s_new;
s_new = "";
s_new = s_new + "$#";
for (int i = 0; i < s.length(); i++) {
s_new = s_new + s[i];
s_new = s_new + '#';
}
s_new = s_new + '\0';
return s_new;
}
int main() {
string s,s_new;
cin >> s;
s_new = mk_new(s);
int id = 0;
int mx = 0;
int Max_len = -1;
vector<int> P(s_new.length());
for (int i = 1; i < s_new.length(); i++) {
if (i < mx) {
P[i] = min(P[2 * id - i], mx - i);
}
else {
P[i] = 1;
}
while (s_new[i - P[i]] == s_new[i + P[i]]) {
P[i]++;
}
if (mx < i + P[i]) {
mx = i + P[i];
id = i;
}
if (mx == s_new.length() - 1) {
Max_len = P[i] - 1;
break;
}
}
cout<< 2*s.length() -Max_len;
return 0;
}
发表于 2019-05-10 10:32:02
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-28 23:31:52
-
2022-09-07 21:01:32 -
2022-09-03 18:47:49 -
2022-09-03 18:47:04 -
2022-09-01 19:42:09
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
