Manacher算法——字符串最长回文子串问题O(N)

最长回文子串

package Manacher

import (
	"math"
	"math/rand"
	"testing"
	"time"
)

// Manacher算法 解决最长回文子串问题
// abcba    abba 长度为奇数和长度为偶数的回文都可以
// 可以认为有一个轴  在实的位置或虚的位置
// Manacher 解决在一个字符串中最长回文子串有多大这个问题
// 最长回文子序列是动态规划的问题，子串必须是连续的
// 回文  DNA是一些序列，可以认为是字符串，DNA的一些基因片段具有回文属性，能找到一些生理学的意义

// 暴力解，每个位置i 求以i为中心的回文串长度,不一定找的完整，因为虚轴被忽略了，所以只能找到长度为奇数的回文串
// 优化：  在每个字符中间插入同一个字符



func manacher(s string) int {
	if len(s) == 0 {
		return 0
	}
	str  := manacherString(s)  // "12132" -> "#1#2#1#3#2#"
	pArr := make([]int,len(str))
	C    := -1
	// 讲述中：R代表最右的扩成功的位置
	// coding：最右的扩成功位置的，再下一个位置
	R    := -1
	max := math.MinInt
	for i := 0; i < len(str); i++ { // 0 1 2
		// R第一个违规的位置，i>= R
		// i位置扩出来的答案，i位置扩的区域，至少是多大。
		pArr[i] = 1
		if R > i {
			pArr[i] = Min(pArr[2*C - i], R - i)
		}
		for i + pArr[i] < len(str) && i - pArr[i] > -1 {
			if str[i + pArr[i]] == str[i - pArr[i]] {
				pArr[i]++
			}else {
				break
			}
		}
		if i + pArr[i] > R {
			R = i + pArr[i]
			C = i
		}
		max = Max(max,pArr[i])
	}
  return max - 1
}

func manacherString(str string) []byte {  // todo 处理中文可能会发生乱码
	res := make([]byte,len(str) * 2 + 1)
	index := 0
	for i := 0; i != len(res); i++ {
			if (i & 1) == 0 {
				res[i] = '#'
			}else{
				res[i] = str[index]
				index++
			}
	}
	return res
}

func Min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
func Max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func right(s string) int {
	if s == "" || len(s) == 0 {
		return 0
	}
	str := manacherString(s)
	max := 0
	for i := 0; i < len(str); i++ {
		L := i - 1
		R := i + 1
		for L >= 0 && R < len(str) && str[L] == str[R] {
			L--
			R++
		}
		max = Max(max, R - L -1)
	}
	return max / 2
}

func getRandomString( possibilities, size int) string  {
	rand.Seed(time.Now().UnixNano())
	ans := make([]byte,rand.Int() % size +1)
	for i := 0; i < len(ans); i++ {
		ans[i] = byte(rand.Int() %possibilities + 'a')
	}
	return string(ans)
}

func TestManacher(t *testing.T)  {  // todo 处理中文可能会发生乱码
	possibilities := 50
	strSize := 200
	testTimes := 500000
	t.Log("test begin")
	for i := 0; i < testTimes; i++ {
		str := getRandomString(possibilities,strSize)
		if a, b := manacher(str), right(str); a != b {
			t.Fatal(str,a,b)
			return
		}
	}
	t.Log("test finish")
}






func shortestEnd(s string) string { // todo 处理中文可能会发生乱码
	if len(s) == 0 {

	}
	str := manacherString(s)
	pArr := make([]int,len(str))
	C := -1
	R := -1
	maxContainsEnd := -1
	for i := 0; i != len(str); i++ {
		pArr[i] = 1
		if R > i {
			pArr[i] = Min(pArr[2 * C - i], R - i)
		}
		for i + pArr[i] < len(str) && i - pArr[i] > -1 {
			if str[i+ pArr[i]] == str[i-pArr[i]] {
				pArr[i]++
			}else {
				break
			}
		}
		if i + pArr[i] > R {
			R = i + pArr[i]
			C = i
		}
		if R == len(s) {
			maxContainsEnd = pArr[i]  // 回文半径
			break
		}
	}
	res := make([]byte,len(str) - maxContainsEnd + 1)
	for i := 0; i < len(res); i++{
		res[len(res)- i -1] = str[i *2 + 1]
	}
	return string(res)
}