#952095 (Go) No.273 回文分解

提出ソース

結果

問題	No.273 回文分解
ユーザー	草苺奶昔
提出日時	2024-02-18 02:47:46
言語	Go (1.22.1)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	11,671 bytes
コンパイル時間	12,565 ms
コンパイル使用メモリ	214,272 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2024-02-18 02:48:00
合計ジャッジ時間	12,225 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,676 KB
testcase_01	AC	1 ms 6,676 KB
testcase_02	AC	1 ms 6,676 KB
testcase_03	AC	1 ms 6,676 KB
testcase_04	AC	1 ms 6,676 KB
testcase_05	AC	1 ms 6,676 KB
testcase_06	AC	1 ms 6,676 KB
testcase_07	AC	2 ms 6,676 KB
testcase_08	AC	1 ms 6,676 KB
testcase_09	AC	1 ms 6,676 KB
testcase_10	AC	1 ms 6,676 KB
testcase_11	AC	1 ms 6,676 KB
testcase_12	AC	1 ms 6,676 KB
testcase_13	AC	1 ms 6,676 KB
testcase_14	AC	1 ms 6,676 KB
testcase_15	AC	1 ms 6,676 KB
testcase_16	AC	1 ms 6,676 KB
testcase_17	AC	2 ms 6,676 KB
testcase_18	AC	1 ms 6,676 KB
testcase_19	AC	1 ms 6,676 KB
testcase_20	AC	1 ms 6,676 KB
testcase_21	AC	1 ms 6,676 KB
testcase_22	AC	1 ms 6,676 KB
testcase_23	AC	2 ms 6,676 KB
testcase_24	AC	1 ms 6,676 KB
testcase_25	AC	1 ms 6,676 KB
testcase_26	AC	1 ms 6,676 KB
testcase_27	AC	2 ms 6,676 KB
testcase_28	AC	1 ms 6,676 KB
testcase_29	AC	1 ms 6,676 KB
testcase_30	AC	2 ms 6,676 KB
testcase_31	AC	1 ms 6,676 KB
testcase_32	AC	1 ms 6,676 KB
testcase_33	AC	1 ms 6,676 KB
testcase_34	AC	2 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	// yuki263()
	yuki273()
	// yuki2606()
	// P3649()
	// P5496()
}

func demo() {
	pt := NewPalindromicTree()
	pt.AddString("eertree")

	fmt.Println(pt.Size() - 2)     // 本质不同回文子串个数(不超过O(n))
	fmt.Println(pt.GetFrequency()) // 每个顶点对应的回文串出现的次数
	for pos := 0; pos < pt.Size(); pos++ {
		res := pt.GetPalindrome(pos)
		fmt.Println(res)
	}
}

// CF 932G
// 分割一个字符串，要求分割的每一部分都是偶回文串。求合法的分割方案数。

// P4762 [CERC2014] Virus synthesis
// https://www.luogu.com.cn/problem/P4762

// P3649 [APIO2014] 回文串
// https://www.luogu.com.cn/problem/P3649
// !对所有不同的回文子串,求出(回文长度*回文出现次数)的最大值
func P3649() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var s string
	fmt.Fscan(in, &s)
	T := NewPalindromicTree()
	T.AddString(s)

	freq := T.GetFrequency()
	res := 0
	for pos := 2; pos < len(freq); pos++ {
		node := T.GetNode(pos)
		res = max(res, int(node.Length)*freq[pos])
	}
	fmt.Fprintln(out, res)
}

// P5496 【模板】回文自动机（PAM）
// https://www.luogu.com.cn/problem/P5496
// 每个位置结尾的回文子串个数(这个节点所表示的回文串中，有多少个后缀也是回文)
// nodes[ch].num = nodes[nodes[ch].fail].num + 1;
func P5496() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var s string
	fmt.Fscan(in, &s)

	T := NewPalindromicTree()

	res := make([]int32, len(s))       // 每个位置结尾的回文子串个数
	counter := make([]int32, len(s)+2) // !统计每个回文树上每个位置结尾的回文子串个数
	for i := 0; i < len(s); i++ {
		curChar := s[i]
		if i >= 1 {
			curChar = (s[i]-97+byte(res[i-1]%26))%26 + 97
		}

		pos := T.Add(int32(curChar))
		link := T.Nodes[pos].Link
		counter[pos] = counter[link] + 1 // !转移
		res[i] = counter[pos]
		fmt.Fprint(out, res[i], " ")
	}
}

// 能否划分成三段回文
// https://leetcode.cn/problems/palindrome-partitioning-iv/description/

// P4287 [SHOI2011] 双倍回文
// https://www.luogu.com.cn/problem/P4287

// No.263 Common Palindromes Extra
// 求两个字符串的公共回文子串的个数 n<=5e5
// https://yukicoder.me/problems/no/263
func yuki263() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var s, t string
	fmt.Fscan(in, &s, &t)
	T := NewPalindromicTree()
	T.AddString(s + "><" + t)
	dps := make([]int, T.Size())
	dpt := make([]int, T.Size())
	lenS := int32(len(s))
	for i := 0; i < T.Size(); i++ {
		for _, j := range T.Nodes[i].Indexes { // 回文出现位置
			if j < lenS {
				dps[i]++
			} else if j >= lenS+2 {
				dpt[i]++
			}
		}
	}

	res := 0
	for i := T.Size() - 1; i >= 2; i-- { // 按照拓扑序遍历本质不同回文
		res += dps[i] * dpt[i]
		dps[T.Nodes[i].Link] += dps[i]
		dpt[T.Nodes[i].Link] += dpt[i]
	}
	fmt.Fprintln(out, res)
}

// No.273 回文分解
// https://yukicoder.me/problems/no/273
// !将字符串s分成若干段,保证每段都是回文串(段数>=2)
// 求最长的回文串的最大值
// 2<=len(s)<=1e5
func yuki273() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	const INF int = 1e18

	var s string
	fmt.Fscan(in, &s)
	n := len(s)
	maxLen := make([]int, n+2) // dp1[i]表示以i回文树位置为结尾的最长回文串的长度
	for i := range maxLen {
		maxLen[i] = -INF
	}
	dp := make([]int, n+1) // dp2[i]表示前i个字符的最长回文串的长度
	for i := range dp {
		dp[i] = -INF
	}
	dp[0] = 1

	T := NewPalindromicTree()
	for i, c := range s {
		T.Add(c)

		updated := T.UpdateDp(
			// 基于 s[start:i+1] 这一段回文初始化 pos 处的值
			func(pos, start int) {
				if i+1-start == n {
					maxLen[pos] = dp[start] // 段数需要>=2
				} else {
					maxLen[pos] = max(dp[start], i+1-start)
				}
			},
			// 基于 pre 的信息更新 pos 处的值
			func(pos, pre int) {
				if int(T.Nodes[pos].Length) == n {
					maxLen[pos] = max(maxLen[pos], maxLen[pre]) // 段数需要>=2
				} else {
					maxLen[pos] = max(maxLen[pos], max(maxLen[pre], int(T.Nodes[pos].Length)))
				}
			},
		)

		for _, p := range updated {
			dp[i+1] = max(dp[i+1], maxLen[p])
		}
	}

	fmt.Fprintln(out, dp[n])
}

// https://yukicoder.me/problems/no/2606
// 给定一个字符串s.
// 向一个空字符x串插入字符，如果x为回文，则获得 x的长度*x在s中出现的次数 的分数.
// 求最终可能的最大分数.
// n<=2e5
func yuki2606() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var s string
	fmt.Fscan(in, &s)

	T := NewPalindromicTree()
	T.AddString(s)
	counter := T.GetFrequency()
	n := T.Size()
	dp := make([]int, n)
	for i := 2; i < n; i++ {
		node := T.GetNode(i)
		count := counter[i]
		length := int(node.Length)
		fail := node.Link
		dp[i] = max(dp[i], dp[fail]+count*length)
	}

	fmt.Fprintln(out, maxs(dp))
}

// 5. 最长回文子串
// https://leetcode.cn/problems/longest-palindromic-substring/
func longestPalindrome(s string) string {
	start, end, maxLen := 0, 0, 0
	tree := NewPalindromicTree()
	for i, c := range s {
		pos := tree.Add(c)
		if int(tree.Nodes[pos].Length) > maxLen {
			maxLen = int(tree.Nodes[pos].Length)
			start, end = i-maxLen+1, i+1
		}
	}
	return s[start:end]
}

// 647. 回文子串-回文子串个数
// https://leetcode.cn/problems/palindromic-substrings/description/
func countSubstrings(s string) int {
	// tree := NewPalindromicTree()
	// ends := make([]int, len(s))      // 每个位置结尾的回文子串个数
	// counter := make([]int, len(s)+2) // !统计每个回文树上每个位置结尾的回文子串个数
	// for i, c := range s {
	// 	pos := tree.Add(c)
	// 	counter[pos] = counter[tree.Nodes[pos].Link] + 1 // !转移
	// 	ends[i] = counter[pos]
	// }
	// res := 0
	// for i := 0; i < len(s); i++ {
	// 	res += ends[i]
	// }
	// return res
	tree := NewPalindromicTree()
	tree.AddString(s)
	counter := tree.GetFrequency()
	res := 0
	for _, v := range counter[2:] {
		res += v
	}
	return res
}

type Node struct {
	Next      map[int32]int32 // 子节点.
	Link      int32           // suffix link，指向当前回文串的最长真回文后缀的位置
	Length    int32           // 结点代表的回文串的长度
	Indexes   []int32         // 哪些位置的最长回文后缀
	deltaLink int32
}

type PalindromicTree struct {
	Ords    []int32
	Nodes   []*Node
	lastPos int32 // 当前字符串(原串前缀)的最长回文后缀
}

func NewPalindromicTree() *PalindromicTree {
	res := &PalindromicTree{}
	res.Nodes = append(res.Nodes, res.newNode(0, -1)) // 奇根，长为 -1
	res.Nodes = append(res.Nodes, res.newNode(0, 0))  // 偶根，长为 0
	return res
}

// !添加一个字符,返回以这个字符为后缀的最长回文串的位置pos.
// 每次增加一个字符，本质不同的回文子串个数最多增加 1 个.
func (pt *PalindromicTree) Add(x int32) int {
	pos := int32(len(pt.Ords))
	pt.Ords = append(pt.Ords, x)
	cur := pt.findPrevPalindrome(pt.lastPos)
	_, hasKey := pt.Nodes[cur].Next[x]
	if !hasKey {
		pt.Nodes[cur].Next[x] = int32(len(pt.Nodes))
	}
	pt.lastPos = pt.Nodes[cur].Next[x]
	if !hasKey {
		pt.Nodes = append(pt.Nodes, pt.newNode(-1, pt.Nodes[cur].Length+2))
		if pt.Nodes[len(pt.Nodes)-1].Length == 1 {
			pt.Nodes[len(pt.Nodes)-1].Link = 1
		} else {
			pt.Nodes[len(pt.Nodes)-1].Link = pt.Nodes[pt.findPrevPalindrome(pt.Nodes[cur].Link)].Next[x]
		}

		if pt.diff(pt.lastPos) == pt.diff(pt.Nodes[len(pt.Nodes)-1].Link) {
			pt.Nodes[len(pt.Nodes)-1].deltaLink = pt.Nodes[pt.Nodes[len(pt.Nodes)-1].Link].deltaLink
		} else {
			pt.Nodes[len(pt.Nodes)-1].deltaLink = pt.Nodes[len(pt.Nodes)-1].Link
		}
	}

	pt.Nodes[pt.lastPos].Indexes = append(pt.Nodes[pt.lastPos].Indexes, pos)
	return int(pt.lastPos)
}

func (pt *PalindromicTree) AddString(s string) {
	if len(s) == 0 {
		return
	}
	for _, v := range s {
		pt.Add(v)
	}
}

// Palindrome Series 优化DP
// https://zhuanlan.zhihu.com/p/92874690
// 在每次调用Add(x)之后使用,更新dp.
//   - init(pos, start): 初始化顶点pos的dp值,对应回文串s[start:i+1].
//   - apply(pos, prePos): 用prePos(fail指针指向的位置)更新pos.
//     返回值: 以S[i]为结尾的回文的位置.
func (pt *PalindromicTree) UpdateDp(init func(pos, start int), apply func(pos, pre int)) (updated []int) {
	i := int32(len(pt.Ords) - 1)
	id := pt.lastPos
	for pt.Nodes[id].Length > 0 {
		init(int(id), int(i+1-pt.Nodes[pt.Nodes[id].deltaLink].Length-pt.diff(id)))
		if pt.Nodes[id].deltaLink != pt.Nodes[id].Link {
			apply(int(id), int(pt.Nodes[id].Link))
		}
		updated = append(updated, int(id))
		id = pt.Nodes[id].deltaLink
	}
	return
}

// 按照拓扑序进行转移.
// from: 后缀连接, to: 当前节点
func (pt *PalindromicTree) Dp(f func(from, to int)) {
	for i := pt.Size() - 1; i >= 2; i-- {
		f(int(pt.Nodes[i].Link), i)
	}
}

// 求出每个顶点对应的回文串出现的次数.
func (pt *PalindromicTree) GetFrequency() []int {
	res := make([]int, pt.Size())
	// !节点编号从大到小，就是 fail 树的拓扑序
	for i := pt.Size() - 1; i >= 1; i-- { // 除去根节点(奇根)
		res[i] += len(pt.Nodes[i].Indexes)
		res[pt.Nodes[i].Link] += res[i] // 长回文包含短回文
	}
	return res
}

// 当前字符的本质不同回文串个数.
func (pt *PalindromicTree) CountPalindromes() int {
	res := 0
	for i := 1; i < pt.Size(); i++ { // 除去根节点(奇根)
		res += len(pt.Nodes[i].Indexes)
	}
	return res
}

// 输出每个顶点代表的回文串.
func (pt *PalindromicTree) GetPalindrome(pos int) []int {
	if pos == 0 {
		return []int{-1}
	}
	if pos == 1 {
		return []int{0}
	}
	var res []int
	// 在偶树/奇树中找到当前节点的回文串
	pt.outputDfs(0, pos, &res)
	pt.outputDfs(1, pos, &res)
	start := len(res) - 1
	if pt.Nodes[pos].Length&1 == 1 {
		start--
	}
	for i := start; i >= 0; i-- {
		res = append(res, res[i])
	}
	return res
}

// 回文树中的顶点个数.(包含两个奇偶虚拟顶点)
// 一个串的本质不同回文子串个数等于 Size()-2.
func (pt *PalindromicTree) Size() int {
	return len(pt.Nodes)
}

// 返回pos位置的回文串顶点.
func (pt *PalindromicTree) GetNode(pos int) *Node {
	return pt.Nodes[pos]
}

func (pt *PalindromicTree) newNode(link, length int32) *Node {
	return &Node{
		Next:      make(map[int32]int32),
		Link:      link,
		Length:    length,
		deltaLink: -1,
	}
}

// 沿着失配指针找到第一个满足 x+s+x 是原串回文后缀的位置.
func (pt *PalindromicTree) findPrevPalindrome(cur int32) int32 {
	pos := int32(len(pt.Ords) - 1)
	for {
		rev := pos - 1 - pt.Nodes[cur].Length
		// !插入当前字符的条件str[i]==str[i-len-1]
		if rev >= 0 && pt.Ords[rev] == pt.Ords[len(pt.Ords)-1] {
			break
		}
		cur = pt.Nodes[cur].Link
	}
	return cur
}

// 当前位置的回文串长度减去当前回文串的最长后缀回文串的长度.
func (pt *PalindromicTree) diff(pos int32) int32 {
	if pt.Nodes[pos].Link <= 0 {
		return -1
	}
	return pt.Nodes[pos].Length - pt.Nodes[pt.Nodes[pos].Link].Length
}

func (pt *PalindromicTree) outputDfs(cur, id int, res *[]int) bool {
	if cur == id {
		return true
	}
	for key, next := range pt.Nodes[cur].Next {
		if pt.outputDfs(int(next), id, res) {
			*res = append(*res, int(key))
			return true
		}
	}
	return false
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func maxs(nums []int) int {
	res := nums[0]
	for _, v := range nums {
		if v > res {
			res = v
		}
	}
	return res
}