package main

import (
    "bytes"
    "fmt"
    "strings"
)

func main() {
    s := "aabbabba"
    fmt.Println(manacher(s))
    // abbabba
}

// 马拉车算法
func manacher(s string) string {
    char := byte('#')
    s = changeStr(s, char)

    // 存储以字符 N[i] 为中心的最长回文字串的最右字符到 N[i] 的长度
    p := make([]int, len(s))
    // mx 之前计算中最长回文子串的右端点的最大值，id 为取得 mx 的回文中心位置
    var id, mx int
    // 最大回文中心位置
    maxCenterIndex := 1

    // 去除边界 ^ $
    for i := 1; i < len(p) - 1; i++ {
        // j 是 i 以 id 为中心的对称点
        j := 2 * id - i

        // i 处在右边界 mx 的左边
        if mx > i {
            if mx - i > p[j] {  // 对称点 j 的回文串没有越界，根据对称关系赋值
                p[i] = p[j]
            } else {            // 越界，则先赋值 mx - i
                p[i] = mx - i
            }
        }

        // 循环比较
        for s[i + p[i]] == s[i - p[i]] {
            p[i]++
        }

        // i 的右边界超出 mx
        if i + p[i] > mx {
            mx = i + p[i]
            id = i
        }

        // 计算最大回文中心位置
        if p[i] > p[maxCenterIndex] {
            maxCenterIndex = i
        }
    }

    // 最大回文串长度
    //maxLength := p[maxCenterIndex] - 1

    // 返回最长回文
    start := maxCenterIndex - p[maxCenterIndex] + 1
    end := maxCenterIndex + p[maxCenterIndex]
    substr := s[start:end]

    return strings.Replace(substr, string(char), "", -1)
}

// 改变字符串
func changeStr(s string, char byte) string {
    var new bytes.Buffer

    new.WriteByte('^')
    for _, b := range []byte(s) {
        new.WriteByte(char)
        new.WriteByte(b)
    }
    new.WriteByte(char)
    new.WriteByte('$')

    return new.String()
}