算法训练营 -- 回文串

描述

给定一个字符串，求出该字符串有多少子串是回文串。

子串：字符串中连续的一段。比如字符串abcd里，bc、abc、a、bcd都是子串。

回文串：字符串倒序写出来和该字符串相同。比如aba，倒序写出来也是aba，故aba是回文串。而abab不是回文串，因为倒过来写是baba。

输入

输入一个字符串。

输出

输出子串是回文串的个数。

样例1输入

abab

样例1输出

6

样例1解释

a1，b1，a2

b2，aba，bab

提示

最长回文子串——Manacher 算法

这篇文章是求最长的回文串的，那么如何求回文串的数目呢？可以发现manacher算法将每个位置为中心能延展出的最长回文串求出来了，那么这个最长回文串的一半（上取整）就是以该点作为中心的回文串数目。

注意答案要用long long。

Manacher算法详解

click here.

解法1：暴力求解(只能得50分)

#!/usr/bin/env pypy3
# encoding=utf-8

def palin(st): # This function is to judge whether the string "st" is a palindrome or not.
    '''
    :param st: the string that is judged
    return : a boolean
    '''
    l = len(st) # The length of the string
    a = True # Define a boolean variation whose defalt is True.
    if l == 1: # If "st" consists of only one character:
        return True # It is definitely a palindrome.
    # ==============================================================
    st_l = list(st) # Convert the string "st" to a list "st_l"
    mid = l // 2 # The rank of the middle point
    if l % 2 == 0: # If 'l' is a double number,
        st_l.insert(mid, '#') # insert a sharp to the middle of the list "st_l"
        # to make the length of the "st_l" a single number
        l = len(st_l) # Update the value of "l"
    # ==============================================================
    i = mid - 1 # From middle to left
    j = mid + 1 # From middle to right
    while ((i >= 0) and (j < l)):
        if st_l[i] != st_l[j]: # If asymmetirc happened,
            a = False # "a" becomes "False".
            break # Break the loop.
        else:
            i -= 1
            j += 1
    return a


def getAnswer(Str):
    le = len(Str)
    cnt = 0  # Count
    for i in range(le):  # Start
        for j in range(i + 1, le + 1):
            h = palin(Str[i: j])
            if (h == True):
                cnt += 1

    return cnt

if __name__ == "__main__":
    print(getAnswer(input()))

---

References

1. 最长回文子串 -- Manacher算法
2. Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 1