首页 > 试题广场 >

最多的回文

[编程题]最多的回文
  • 热度指数:1123 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个字符串s,问该字符串里有多少个长度大于1的连续子串都是回文?
回文:正序的文本内容与倒序的文本内容相同,比如 aa,aba

输入描述:
字符串s,1<=length(s)<=100000


输出描述:
一个整数,该字符串内部有多少个连续子串都是回文
示例1

输入

a

输出

0

说明

没有长度大于1的回文
示例2

输入

abbcbb

输出

4

说明

解释:bb,bbcbb,  bcb, bb
#牛客405350751号的python实现
s=input()
count=0
for i in range(len(s)):
    k=i-1
    r=i+1
    while(k>=0 and r<=len(s)-1 and s[k]==s[r]):   #以当前字符为对称轴向左右扩展
        count=count+1
        k=k-1
        r=r+1
    k=i
    r=i+1
    while(k>=0 and r<=len(s)-1 and s[k]==s[r]):  #以两个字符的中间对称轴
        count=count+1
        k=k-1
        r=r+1
print(count)
     

发表于 2021-05-17 18:36:38 回复(0)
const readline = require("readline")
 
const rl = readline.createInterface({
  input:process.stdin,
  output: process.stdout
})
 
let result = 0
 
rl.on("line", line => {
  if(line.length === 1) {
    console.log(0)
    return
  }
  for(let i = 0; i < line.length; i++) {
    // 以当前字母为对称轴
    for (let j = 1; j < line.length; j++) {
      if (line[i - j] && line[i + j] && line[i - j] === line[i + j]) {
        result += 1
      } else {
        break
      }
    }
    // 以空隙为对称轴
    for (let j = 0; j < line.length; j++) {
      if (line[i - j] && line[i - j + 1] && line[i - j] === line[i + j + 1]) {
        result += 1
      } else {
        break
      }
    }
  }
  console.log(result)
})

发表于 2021-02-08 13:51:28 回复(0)
外层固定右边界,改变左边界,内层固定左边界,改变右边界,对所有子串进行回文检验
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int count = 0;
        for(int i = 0; i < str.length(); i++){
            // 固定右边界
            int left = i, right = str.length() - 1;
            while(left < right){
                // 固定左边界
                int temp_l = left, temp_r = right;
                // 检查str[temp_l:temp_r]是否是回文串
                while(temp_l < temp_r){
                    if(str.charAt(temp_l) != str.charAt(temp_r))
                        break;        // 以temp_l开头temp_r结尾的子串不是回文串
                    temp_l++;
                    temp_r--;
                }
                // 如果右边界到左边界的左边了,说明此时抓出来一个回文串
                if(temp_l >= temp_r) count ++;
                right --;
            }
        }
        System.out.println(count);
    }
}


发表于 2021-01-18 21:00:21 回复(0)
仅从数据层面看,O(N^2)的算法应无法通过,但实际上数据不强,平方级仍可通过。
此处介绍一种字符串哈希结合二分的方法,复杂度O(N*logN)。其实此方法的基础是求字符串最长回文子串。
(1)对字符串正反两向做哈希处理
(2)回文串长度有奇数和偶数两种,求以pos为中心的最长回文子串和以(pos,pos+1)为中心的最长回文子串。
例如以pos为中心最长回文子串长度为2x+1,那么可以得到x个长度超过2的回文子串,例如子串bbabb,那么bab,bbabb为解。
(3)求pos为中心的最长回文子串可以用二分法来降低复杂度。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
string s;
ll n,p=131,hx[100005]={1},hx2[100005],pw[100005]={1},ans=0;
int check1(ll pos)/**< 求以pos为中点的回文串最大长度 */
{
    int l=0,r=min(pos-1,n-pos),mid,best=0;
    while(l<=r)
    {
        mid=(l+r)>>1;/**< 左半段p-mid~p,右半段p~p+mid */
        if(hx[pos-1]-hx[pos-mid-1]*pw[mid]==hx2[pos+1]-hx2[pos+mid+1]*pw[mid])
          l=mid+1,best=mid;
        else
            r=mid-1;
    }
    return best;
}
int check2(ll pos)/**< 求以pos和pos+1为中点的回文串最大长度 */
{
    if(pos==n||s[pos-1]!=s[pos])
        return 0;
    int l=1,r=min(pos,n-pos),mid,best=1;
    while(l<=r)
    {
        mid=(l+r)/2;/**< 左半段p-mid+1~p开始,右半段p+1~p+1+mid */
        if(hx[pos]-hx[pos-mid]*pw[mid]==hx2[pos+1]-hx2[pos+1+mid]*pw[mid])
          l=mid+1,best=mid;
        else
            r=mid-1;
    }
    return best;
}
int main()
{

    int i,j;
    cin>>s;
    n=s.size();
    for(i=1;i<=100000;i++)
        pw[i]=pw[i-1]*p;
    for(i=0;i<s.size();i++)
        hx[i+1]=hx[i]*p+s[i]-'a'+1;
    for(i=n-1;i>=0;i--)
        hx2[i+1]=hx2[i+2]*p+s[i]-'a'+1;
    for(i=1;i<=n;i++)
    {
        int len1=check1(i),len2=check2(i);
        ans+=len1+len2;
    }
    cout<<ans;
    return 0;
}



发表于 2022-01-14 12:15:05 回复(0)
s = input()
count = 0
# 控制字串长度
for i in range(1, len(s)):
    # 控制子串初始字符
    for j in range(len(s) - i):
        str = s[j:(j + i + 1)]
        # 判断回文
        if str == str[::-1]:
            count += 1
print(count)

发表于 2021-09-07 10:03:23 回复(0)
str=input()
len1=len(str)
count=0
forainrange(len1-1):
    b=a+1
    whileb <=len1:
        s=str[a:b:1]
        ifs==s[::-1]andlen(s)>1:
            count+=1
        b+=1
print(count)

发表于 2022-08-19 23:15:07 回复(0)
//双指针
package main
import "fmt"
func extend(s string,i,j,n int) int{
    res :=0
    for i>=0 && j < n && s[i] == s[j]{
        if j-i+1 >1{
            res++
        }
        i--
        j++


    }
    return res
}

func countSubstrings(s string) int {
    result := 0
    for i:=0;i<len(s);i++{
        result += extend(s,i,i,len(s))
        result += extend(s,i,i+1,len(s))
    }
    return result
}

func main (){
    var s string
    fmt.Scanln(&s)
    res := countSubstrings(s)
    fmt.Println(res)
}


发表于 2022-08-02 21:50:33 回复(0)
let s = readline();

let findSequence = (str) => {
        let length = str.length;
        // count表示回文子串的个数
        let count = 0;
        // 构建一个矩阵arr,矩阵的长和宽是字符串的长度
        const arr = new Array(length)
          .fill("F")
          .map(() => new Array(length).fill("F"));
        // i为矩阵的列,j为矩阵的行,arr[i][j]表示当前子字符串是否为回文
        // T表示是回文字符串,F则不是
        for (let i = 0; i < length; i++) {
          for (let j = 0; j <= i; j++) {
            // case1: 单个字符必然是回文的,但本题规定回文子串长度必须大于1,因此count不变
            if (i == j) {
              arr[j][i] = "T";
            } else if (i - j == 1 && str[i] == str[j]) {
              // case2: 子串只有2个字符,如果它们相等,则回文
              count++;
              arr[j][i] = "T";
            } else if (
              i - j > 1 &&
              str[i] == str[j] &&
              arr[j + 1][i - 1] == "T"
            ) {
              // case3: 子串长度大于2,此时不仅要首位2个字符相等,还要保证中间的字符是回文子串
              count++;
              arr[j][i] = "T";
            }
          }
        }
        return count;
      };

print(findSequence(s));

发表于 2022-07-16 12:46:18 回复(0)
#include <iostream>

using namespace std;

int main()
{
    string s; cin >> s;
    int res = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int l = i - 1, r = i + 1;
        while (l >= 0 && r < s.size() && s[l] == s[r])
        {
            l--; r++; res++;
        }
        l = i; r = i + 1;
        while (l >= 0 && r < s.size() && s[l] == s[r])
        {
            l--; r++; res++;
        }
    }
    cout << res << endl;
    
    return 0;
}
发表于 2022-03-05 14:12:27 回复(0)
#include<string.h>
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    char s[5000];
    while (scanf("%s", s)!=EOF)
    {
        int len = strlen(s) - 1, ans = 0, l, r;
        for (int i = 0; i <= len;i++)
        {
            l = i-1;
            r = i + 1;
            while (l>=0&&r<=len&&s[l] == s[r])
            {
                ++ans;
                l--;
                r++;
            }
        }
        for (int i = 0; i <= len; i++)
        {
            l = i;
            r = i + 1;
            while (l >= 0 &&r<=len && s[l] == s[r])
            {
                ++ans;
                l--;
                r++;
            }
        
        }
        cout<<ans;
    }
    
}
发表于 2021-09-06 19:01:34 回复(0)
let str =readline()
let len = str.length
let dp = new Array(len).fill(0).map(()=>new Array(len).fill(true))
let count = 0
for(let i = len - 1;i>= 0;i--) {
    for(let j = i+1;j < len;j++) {
        dp[i][j] = str[i] == str[j] && dp[i+1][j-1]
     }
}
// console.log(dp);
for(let i = 0;i<len;i++) {
    for(let j = i+1;j<len;j++) {
        if(dp[i][j]) {
            count++
        }
    }
}
console.log(count);
发表于 2021-07-08 21:57:22 回复(0)
马拉车回文自动机都不会背的我直接退出来看了一眼解析,发现一个个n*n加判断。。。1e5的数据范围跟1s的时间原来都是假的
发表于 2021-03-27 10:27:38 回复(0)
#include<iostream>
#include<string.h>
#include<string>
using namespace std;

int getSubList(string s, int left, int right, int count) {
    while (left >= 0 && right < s.length() && s[left] == s[right]){
        if (left == right) {
            left--;
            right++;
        }else{
            count++;
            left--;
            right++;
        }
    }
    return count;
}

int main() {
    string test;
    int count = 0;
    cin >> test;
    if (test.length() == 1) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 0; i < test.length(); i++) {
        count = getSubList(test, i, i, count);
        count = getSubList(test, i, i+1, count);
    }
    cout << count << endl;
    system("pause");
}
发表于 2021-03-18 17:09:23 回复(0)
看了别人的讲解有个更简单的做法,回文串有两种bab和aa( 以字符或以两字符间空隙为对称轴 )
所以就有了下面的做法
外循环循环整个字符串
第一个内循环以当前字符为对称轴不断向外延伸,直到遇到不相等的一对
第二个内循环以当前字符和下一字符向外延伸,直到遇到不相等的一对
#include<stdio.h>
#include<string.h>
chars[5007];
intmain()
{
    while(scanf("%s",s)!=EOF)
    {
        int len=strlen(s)-1,ans=0,l,r;
        for(inti=0;i<=len;++i)
        {
            for(l=i-1,r=i+1;l>=0&&r<=len&&s[l]==s[r];--l,++r,++ans)
            ;
            for(l=i,r=i+1;l>=0&&r<=len&&s[l]==s[r];--l,++r,++ans)
            ;
        }
        printf("%d\n",ans);
    }
    return0;
}


发表于 2021-02-05 20:45:58 回复(0)
#include<iostream>
#include<string>

using namespace std;

int main()
{
    string s;
    int ret=0;
    while(cin>>s);
    for(int i=0;i<s.size();i++)
    {
        int left = i, right =s.size()-1;
        while(left<right)
        {
            int t_left =left, t_right = right;
            while(t_left<t_right)
            {
                if(s[t_left]!=s[t_right])    {break;}
                t_left++;t_right--;
                
            }
            if(t_right<=t_left)    {ret++;}
            right--;
        }
    }
    
    cout<<ret<<endl;
    return 0;
}
发表于 2021-01-18 15:22:24 回复(0)
//无脑法
import java.util.Scanner;

public class Main {

    public static int f(String s) {
        int r = 0;
        for (int i = 0; i < s.length(); i++) {
            int a = i - 1;
            int b = i + 1;
            while (a >= 0 && b < s.length() && s.charAt(a) == s.charAt(b)) {
                if (b - a - 1 > 1) {
                    r++;
                }
                a--;
                b++;

            }
            if (b - a - 1 > 1) {
                r++;
            }
            a = i;
            b = i + 1;
            while (a >= 0 && b < s.length() && s.charAt(a) == s.charAt(b)) {
                if (b - a - 1 > 1) {
                    r++;
                }
                a--;
                b++;

            }
            if (b - a - 1 > 1) {
                r++;
            }
        }
        return r;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String s = scanner.nextLine();
            System.out.println(f(s));
        }
    }

}

发表于 2021-01-16 17:38:02 回复(0)