回文子串

[编程题]回文子串

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

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

("回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。)

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

数据范围：字符串长度满足 $1 \le n \le 50 \$

输入描述:

输入一个字符串S 例如“aabcb”(1 <= |S| <= 50), |S|表示字符串S的长度。

输出描述:

符合条件的字符串有"a","a","aa","b","c","b","bcb"

所以答案:7

示例1

输入

aabcb

输出

算法知识视频讲解

Python

扁鹊扁鹊

import sys
def isHuiwen(string):
    if len(string)==1:
        return True
    i,j = 0,len(string)-1
    while i<j:
        if string[i] != string[j]:
            return False
        i+=1
        j-=1
    return True
def countNum(string):
    res = 0
    for i in range(len(string)-1,-1,-1):
        if isHuiwen(string[i:len(string)]):
            res+=1
    return res
while True:
    #动态规划问题：
    #dp[i]表示在第i个位置时字符串有多少个回文子串
    #状态转移方程：
    #dp[i+1] = dp[i] + countNum(str[:i])
    string = input().strip()
    dp=[0 for _ in range(len(string))]
    dp[0]=1
    for i in range(1,len(string)):
        dp[i] = dp[i-1]+countNum(string[:i+1])
    print(dp[-1])

发表于 2020-08-19 22:25:48 回复(0)

Python

handsomefellow

def num_substr(s):
    res = 0
    if len(s)<=1:
        print(len(s))
        return len(s)
    for length in range(len(s),0,-1):
        for i in range(len(s)-length+1):
            now_s = s[i:i+length]
            if now_s == now_s[::-1]:
                res+=1
    print(res)
    return res

if __name__ == '__main__':
    import sys
    s = sys.stdin.readline().strip()
    num_substr(s)

发表于 2020-06-11 12:47:08 回复(0)

Python

EnvyEvil

str = input()

#  判断是否是回文
def is_palindrome(str):
    is_palindrome_flag = True
    for i in range(len(str) // 2):
        if str[i] is not str[-i - 1]:
            is_palindrome_flag = False
    return is_palindrome_flag

res = 0
# 将str变成二维，找到str[x：y+1]的切片
for x in range(0, len(str)):
    for y in range(x, len(str)):
        if is_palindrome(str[x:y + 1]):
            res += 1

print(res)

发表于 2019-09-17 10:10:50 回复(0)

Python

从不嘻嘻哈哈。

a = input()
count = 0
i = 0
while i < len(a):
    j = i + 1
    while j <= len(a):
        if a[i:j] == a[-(len(a)-j+1):i:-1]+a[i]:
            count += 1
        j += 1
    i += 1
print(count)

发表于 2019-09-05 16:12:04 回复(0)

Python

欧巴禾

def solve(word):
if not word:
return False
index = 0
n = len(word)
while index<=n-index-1:
if word[index]==word[n-index-1]:
index+=1
else:
return False
return True

s = input()
number = 0
for i in range(len(s)):
for j in range(i+1, len(s)+1):
word = s[i:j]
if solve(word):
number+=1
print(number)

发表于 2019-08-10 10:07:34 回复(0)