首页 > 试题广场 >

统计回文

[编程题]统计回文

热度指数：35693 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。
例如：
A = “aba”，B = “b”。这里有4种把B插入A的办法：
* 在A的第一个字母之前: "baba" 不是回文
* 在第一个字母‘a’之后: "abba" 是回文
* 在字母‘b’之后: "abba" 是回文
* 在第二个字母'a'之后 "abab" 不是回文
所以满足条件的答案为2

输入描述:

每组输入数据共两行。
第一行为字符串A
第二行为字符串B
字符串长度均小于100且只包含小写字母

输出描述:

输出一个数字，表示把字符串B插入字符串A之后构成一个回文串的方法数

示例1

输入

aba
b

输出

算法知识视频讲解

^_^smile＆青春

import java.util.*;

public class Main{

public static void main(String args[]){

Scanner sc = new Scanner(System.in);

while(sc.hasNext()){

String a = sc.nextLine();

String b = sc.nextLine();

int m = 0;

for(int i=0;i<a.length()+1;i++){

String str = a.substring(0,i)+b+a.substring(i,a.length());

StringBuffer sb = new StringBuffer(str);

if(sb.reverse().toString().equals(str)){

m++;

}

System.out.print(m);

}

发表于 2016-08-08 13:55:16 回复(4)

Python

麻瓜工程师

n,m,count = input(),input(),0
for i in range(len(n)+1):
    s = n[:i] + m + n[i:]
    if s[::-1] == s:
        count += 1
print(count)

回文字符串的特征就是逆序和正序相等，因此只需要判断有几种插入形式，对于每种插入形式，判断一下逆序正序是否相等即可

发表于 2018-07-04 00:01:36 回复(0)

Java

安顾

//没有拼接，而是两个指针分别从头尾0，m+n-1，根据插入位置计算分别是哪个字符
//效率上应该会快点，因为在头尾就不符合就立即退出了
import java.util.*;
public class Main {    
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);    
        while(input.hasNext()){
            String a = input.next();
            String b = input.next();
            int n = a.length(),m=b.length();
            int ans = 0;
            for(int i=0;i<=n;i++){//insert pos
                int p=0,q=m+n-1;
                while(p<=q){
                    if(get(p,i,a,b)==get(q,i,a,b)){
                        p++;q--;
                    }else break;
                }
                if(p>q) ans++;
            }            
            System.out.println(ans);
        }
    }
    public static char get(int index,int insert,String a,String b){
        if(index<insert){
            return a.charAt(index);
        }else if(index>=insert&&index<insert+b.length()){
            return b.charAt(index-insert);
        }else{
            return a.charAt(index-b.length());
        }
    }
}

发表于 2017-09-09 20:24:28 回复(0)

牛客677436号

import java.util.*;
public class Main{
    public static boolean isHuiWen(String str){
        int i=0;
        int j=str.length()-1;
        while(i<j){
            if(str.charAt(i)!=str.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    public static int number(String a,String b){
        int count=0;
        int len=a.length();
        for(int i=0;i<=len;i++){
            String str=a.substring(0,i)+b+a.substring(i,len);
            if(isHuiWen(str)){
                count++;
            }
        }
        return count;
    }
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        while(s.hasNext()){
            String a=s.next();
            String b=s.next();
            System.out.println(number(a,b));
        }
    }
}

发表于 2016-08-11 19:55:34 回复(0)

Java

天山雪狼

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String str1 = sc.nextLine();
			String str2 = sc.nextLine();
			int len = str1.length();
			int n = 0;
			for (int i = 0; i <= len; i++) {
			String str4 = str1.substring(0, i) + str2 + str1.substring(i);
			String str5 = new StringBuffer(str4).reverse().toString();
			if (str4.equals(str5)) {
			n++;
			}
			}
			System.out.println(n);
		}
	}
}

发表于 2017-08-10 16:08:15 回复(1)

Java

黄小斜

最喜欢这种题了
import java.util.Scanner;
public class Main{
        public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.nextLine();
        String b = scanner.nextLine();
        System.out.println(insert(a, b));
    }

    public static int insert(String a, String b) {
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0;i <= a.length();i ++) {
            if (i == 0) {

            }else {
                sb.append(a.substring(0, i));
            }
            sb.append(b);
            if (i == a.length()) {

            }else {
                sb.append(a.substring(i, a.length()));
            }
            if (legal(sb.toString())) {
                cnt ++;
            }
            sb = new StringBuilder();
        }
        return cnt;
    }

    public static boolean legal(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i ++;
            j --;
        }
        return true;
    }
}

发表于 2018-05-21 14:06:37 回复(0)

JSnowy

import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        //System.out.print("请输入第一个字符串：");
        String s1 = sc.nextLine();
        //System.out.print("请输入第二个字符串：");
        String s2 = sc.nextLine();
        //获取第一行字符串的长度
        int length = s1.length();
        //计数
        int count=0;
        for(int i=0;i<=length;i++){
        StringBuffer sb = new StringBuffer(); 
        StringBuffer sb2 = new StringBuffer(); 
        sb=sb.append(s1).insert(i,s2);
        sb2=sb2.append(s1).insert(i,s2).reverse();
        String s3=sb.toString();
        String s4=sb2.toString();
        //System.out.println(s3+"/"+s4+"/"+s3.equals(s4));
        if(s3.equals(s4)){
            count++;
        }
    }
        System.out.print(count);
    }
}

1、Stringbuffer类中有两个方法，一个是反转，可以确定是否是回文数。一个是插入字符串，两个参数，一个是位置，一个是字符串。

2、最开始一直错，我把sb2=sb.reverse()，故sb2.toString().equals(sb.toString())一直是true。根本原因在于忘记是引用类型，这样做，会指向同一个地址。所以只能重新创建一个sb2，进行append s1 和insert s2，并且对其反转。最后判断两个字符串的值是否相同，相同则计数。

发表于 2018-05-09 11:00:04 回复(0)

Jason_liu


	import java.util.Scanner;



	





	public class Main {



	    public static void main(String[] args) {



	        Scanner sc = new Scanner(System.in);



	        while (sc.hasNext()) {



	            int num = 0;



	            String strA = sc.nextLine();



	            String strB = sc.nextLine();



	            for (int i = 0; i <= strA.length(); i++) {



	                StringBuffer strC=new StringBuffer(strA);



	                strC.insert(i, strB);



	                if ((strC.toString()).equals(strC.reverse().toString())) {



	                    num++;



	                }



	            }



	            System.out.println(num);



	        }



	        sc.close();



	    }



	}

发表于 2018-01-25 16:47:10 回复(0)

C/C++

卡玛酱

#include <iostream>
#include <string>
using namespace std;
bool isSymmetry(string s){
	int n=s.size();
	if(n==1){
		return true;
	}else{
		for(int i=0,j=n-1;i<j;i++,j--){
			if(s[i]!=s[j]){
				return 	false;
			}
		}
		return true;
	}
}
int main(){
	int cnt=0;
	string A,B,temp;
	cin>>A>>B;
	for(int i=0;i<A.size()+1;i++){
		temp=A.substr(0,i)+B+A.substr(i);
		if(isSymmetry(temp)){
			cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}

发表于 2017-08-24 21:33:36 回复(0)

Java

lmz9509

/*
思想：首先写一个回文字符串的判断方法，然后分别将B字符串插入到A的不同位置，把每次生成的字符串进行回文判断
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
//import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String A = br.readLine();
        String B = br.readLine();
        int count = 0;
        for(int i = 0;i<=A.length();i++){
            StringBuffer sb = new StringBuffer();
            sb.append(A.substring(0,i));
            sb.append(B);
            sb.append(A.substring(i,A.length()));
            if(isHui(sb.toString()))
                count++;
        }
        System.out.println(count);
    }
    
    public static boolean isHui(String str){
        //两边向内的方法
        if(str.length()==0)return false;
        if(str.length()==1)return true;
        int left = 0,right = str.length()-1;
        while(left<right){
            if(str.charAt(left) == str.charAt(right)){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }
}

发表于 2020-05-11 14:13:23 回复(0)

峰峰的牛客

//详情请点击博客链接（链接在最下方）
import java.util.Scanner;

public class Statistical_Palindrome2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        int count=0;
        //第一步：截取插入并连接字符串
        //(这里用StringBuilder能解决String不可变性的短板，不用StringBuffer的原因是用不着线程安全效率快)
        for (int i = 0; i <= s1.length(); i++) { 
            StringBuilder s = new StringBuilder(s1);
            s.insert(i, s2); //通过for循环在s1的每个位置都插入得到所有可能出现的字符串
            if(isPalindromic(s)){
                count++;
            }
        }
        System.out.println(count);
    }
    //第二步：判断一个字符串是否是回文字符串
    public static boolean isPalindromic(StringBuilder s) {
        int i = 0;
        int j = s.length() - 1;
        while (i <= j) {
            //取出新得到的字符串挨个字符进行比较
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}


————————————————
版权声明：本文为CSDN博主「峰回路转」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44840148/article/details/105123181

发表于 2020-03-26 17:29:11 回复(0)

wwl亮亮

#include <bits/stdc++.h>
using namespace std;
inline char getForChar(string &s1, string &s2, int inser, int index){
    int ss2 = s2.size();
    if(inser>index)
        return s1[index];
    else if(inser+ss2>index)
        return s2[index-inser];
    else return s1[index-ss2];
}
int huiwen(string &s1,string &s2){
    int ss1 = s1.size();
    int ss2 = s2.size();
    int begin = 0;
    int end = ss1+ss2-1;
    int count = 0;
    for(int inser = 0; inser<=ss1; ++inser){
        begin = 0;
        end = ss1+ss2-1;
         while(begin<=end){
             if(getForChar(s1,s2,inser,begin)!=getForChar(s1,s2,inser,end)){
                 break;
             }
             else {
                 begin++;
                 end--;
             }
         }
         if(begin>=end)
              count++;
    }
    return count ;
}


int main(){
    string str1,str2;
    getline(cin,str1);
    getline(cin,str2);
    cout << huiwen(str1,str2);
    return 0;
}

最好不要去复制字符串

发表于 2019-08-14 10:19:17 回复(0)

tw-luo

#include<iostream>
#include<string>
using namespace std;
bool TractString(string s)
{
    int i = 0, j = s.length()-1;
    while (1)
    {
        if (s[i] != s[j])
            return false;
        i++;
        j--;
        if (i >= j)
            break;
    }
    return true;
}
int main()
{
    string s1, s2;
    int rec=0;
    cin >> s1>>s2;
    for (int i = 0; i <=s1.length(); i++)
    {
        string s3 = { "" };
        for (int j = 0; j <s1.length(); j++)
        {
            if (j!=i)
                s3 += s1[j];
            else
            {
                s3 += s2;
                s3 += s1[j];
            }
        }
        if (i == s1.length())
            s3 = s1 + s2;
        if (TractString(s3))
            rec++;
    }
    cout << rec << endl;
    return 0;
}

发表于 2019-04-12 19:40:29 回复(0)

C/C++

Senjie

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n=0;
    string A,B;
    cin>>A>>B;
    for(int i=0;i<=A.length();i++)
    {
        string a=A;
        a.insert(i,B);
        string b=a;
        reverse(a.begin(),a.end());
        if(a==b)    n++;
    }
    cout<<n<<endl;
}

编辑于 2019-01-30 15:40:57 回复(0)

心碎，人不在

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#define NUM 1024
int Judge(char *src)
{
int len = (int)strlen(src);
char *p = src;
char *q = src + len - 1;
int i;
for(i = 0; i < len/2 + 1; i++)
{

if(*p != *q)
{
return 0;
}
p++;
q--;
}
return 1;
}

int main()
{
char *p = (char *)malloc(NUM*sizeof(char));
char *q = (char *)malloc(NUM*sizeof(char));
char *stor = (char *)malloc(NUM*sizeof(char));
int x, i, num = 0, len;
scanf("%s", p);
scanf("%s", q);
len = strlen(p);
strcpy(stor, p);
for(x = 0; x <= len; x++)
{
for(i = strlen(p); i >= x; i--)
{
*(p + i + strlen(q)) = *(p + i);
}
strncpy(p + x, q, strlen(q));
if(Judge(p) == 1)
{
num++;
}
strcpy(p, stor);
}
printf("%d\n", num);
free(p);

free(q);

free(stor);

}

发表于 2018-11-29 11:04:23 回复(0)

狂奔的蜗牛TX

#include<algorithm>
#include<iostream>
#include<vector>
#include<string>

using namespace std;
bool isValidPalindrome(string s)
{     int l = 0, r = s.size() - 1;     bool flag = true;     while (l <= r)     {         if (s[l] != s[r]){ flag = false; break; }         else{ l++; r--; }     }     return flag;
}
int main()
{     string A, B; cin >> A >> B;     int cnt = 0;     for (int i = 0; i <= A.size(); i++)     {         string tmp=A;         tmp.insert(i,B);                  if (isValidPalindrome(tmp))             cnt++;         else             continue;     }     cout << cnt << endl;
}

发表于 2018-09-03 17:29:07 回复(0)

cqu后起之秀

//写好了这个才看到别人答案直接用一个insert就解决了  笑哭
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
using namespace std;
bool isb(string s){//判断回文
    string s1=s;
    int len=s.length();
    for(int i=0;i<len;i++){
        s1[len-1-i]=s[i];
    }
    return s==s1;
}
string ch2str(char ch){//将char转化为string
    string str;
    stringstream ss;
    ss << ch;
    str = ss.str();
    return str;
}
int main(){
    string A,B,temp;
    int cnt=0;//cnt表示结果
    cin>>A>>B;
    int a=A.length();
    vector<string>ss(a);
    for(int i=0;i<a;i++){//将A的字母单个拆分转化成string存在vector<string>ss(A.length())中
         ss[i]=ch2str(A[i]);
    }
    for(int i=0;i<a;i++){
        //cout<<" i: "<<i ;
        ss[i]+=B;//用 ch2str(A[i])+B 替换掉ss[i]
        //cout<<"  ss"<<"["<<i<<"]: "<<ss[i];
        
        for(int j=0;j<a;j++){//替换完再按顺序拼接,存进temp
            
            temp+=ss[j];
            //cout<<"  temp: "<<temp;
            
        }
        ss[i]= ch2str(A[i]);//复原ss[i]
        
        if(isb(temp)){
            cnt++;
            //cout<<" cnt "<<cnt;
        }
        temp.clear();
    }
    cout<<endl;

    if(isb(B+A)){cnt++;}//前面的情况差B完全插在A的最前面这一种
    cout<<cnt<<endl;
    
    return 0;
}

发表于 2018-08-22 03:05:00 回复(2)

C/C++

晓色竹韵

#include <iostream>
#include <string>
using namespace std;
bool huiwen(string str1)
{
int length=str1.length();
for(int i=0;i<length/2;i++)
if(str1[i]!=str1[length-1-i])
return false;
return true;
}
int main()
{
string str1,str2,temp;
int count=0,len;
cin>>str1>>str2;
len=str1.length()+1;
temp=str1;
for(int i=0;i<len;i++)
{
str1=temp;
str1.insert(i,str2);
if(huiwen(str1))
count++;
}
cout<<count<<endl;

return 0；
}

编辑于 2018-07-23 21:31:05 回复(0)

Python

yzdeng

a=input()
b=input()

#首先考虑将b插入a
n=len(a);m=len(b);count=0
l=''
for i in range(n+1):
    l=a[:i]+b+a[i:]
    #判断l是否回文
    flag=True
    for j in range(n+m//2):
        if l[j]!=l[n+m-1-j]:
            flag=False
    if flag==True:
        count+=1
print(count)

发表于 2018-05-18 21:53:30 回复(0)

LSur

s = input()
a = input()
connect = '' 
num = 0
for i in range(0,len(s)+1):
    if i == 0:
        connect = a+s
    elif i == len(s):
        connect = s+a
    else:
        connect = s[0:i]+a+s[i:len(s)]
    if connect == connect[::-1]:
        num += 1
print(num)

这题很简单，时间主要用来思考如何让代码看上去更简洁更美观上了。
然而看到有用两行Python大法的大神，无奈自己还是太弱鸡。

编辑于 2018-04-07 13:30:27 回复(0)