Manacher算法详解

2019-06-08 本文已影响0人拜仁的月饼

目录结构如下：

引入
Manacher算法详解
例题
References

1. 问题引入

最长回文子串（Longese palindrome substring, LPS）是一个经典算法问题。这个问题一个常用解法是Manacher算法。

LPS问题：在一个字符串中，找到最长回文子串。

首先，我们要先明白什么叫回文串（Palindrome）。

根据词典^[1]的定义，回文串指的是“顺着念和倒着念都一样的词语、诗句等”（a word or group of words that is the same when you read it forwards from the beginning or backwards from the end）。

举例子，以下都可以算做回文串：

里贝里（我仁国王）
12345654321
a （单个字母也算）

用暴力求解可以解出来。方法是首先求出字符串的所有子串，然后一个一个比对，看是否为回文串。

暴力求解可实现代码如下（Python）：

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" become "False".
            break # Break the loop.
        else:
            i -= 1
            j += 1
    return a

如上的函数可以求解一个字符串是否为回文串。

暴力求解的算法很容易理解，但是它的问题也很明显：过于复杂。因为，对于一个长度为n的字符串而言，有n²个子串，而它们的平均长度为n\2，如果对每一子串进行比较，那么复杂度为O(n²*n\2) = O(n³)。

那么，暴力求解是否可以改进？答案是肯定的。

2. Manacher算法详解

其实在上面的函数中，我已考虑Palindrome的一个性质：Parlindrome沿对称轴呈两边对称。如果字符串s的长度l为单数，那么对称轴位于正中间的点s[(l - 1) / 2]处；如果字符串s长度l为双数，那么对称轴位于s[l/2 - 1]与s[l/2]之间的缝隙之间。

那么，以上代码的逻辑就是：以中点为轴，设两个循环i和j，i以中点为起点向左走，每次走一格，走到i = 0为止；j以中点为起点向右走，每次走一格，走到j = l - 1为止。i和j同时走。如果i和j的每一步都相等，那么字符串s即为Palindrome。

这样一来，时间复杂度降为O(n²)。

但是，这样求解还有一个问题：

奇数和偶数要分情况讨论
很多子串被重复计算

是否有一种办法，对如上方法再改进，将时间复杂度降为O(n)？

就是Manacher算法！

Manacher算法...

3. 例题

描述

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

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

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

输入

输入一个字符串。

输出

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

样例1输入

abab

样例1输出

样例1解释

a1，b1，a2

b2，aba，bab

解法1：暴力求解

#!/usr/bin/env pypy3
# coding: 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" become "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()))