给定一个字符串s,问该字符串里有多少个长度大于1的连续子串都是回文?
回文:正序的文本内容与倒序的文本内容相同,比如 aa,aba
字符串s,1<=length(s)<=100000
一个整数,该字符串内部有多少个连续子串都是回文
a
0
没有长度大于1的回文
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)
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) })
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); } }
#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; }
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) }
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));
#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; }