Function stringCollection

copypasta/strings.go:27–698

* 字符串问题的特殊性： 不同子串之间会共享一些局部信息，巧妙地利用这些局部信息可以设计出更加高效的算法。 todo NOI 一轮复习 II：字符串 https://www.luogu.com.cn/blog/ix-35/noi-yi-lun-fu-xi-ii-zi-fu-chuan 金策 字符串算法选讲 https://www.bilibili.com/video/BV11K4y1p7a5 https://www.bilibili.com/video/BV19541177KU PDF 见 misc TIPS: 若处理原串比较困难，不妨考虑下反转后的串 https://codefo

()

*/

func stringCollection() {
	min := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}
	max := func(a, b int) int {
		if a >= b {
			return a
		}
		return b
	}

	// 注：如果 s 是常量的话，由于其在编译期分配到只读段，对应的地址是无法写入的
	unsafeToBytes := func(s string) []byte { return *(*[]byte)(unsafe.Pointer(&s)) }
	unsafeToString := func(b []byte) string { return *(*string)(unsafe.Pointer(&b)) }

	// 返回 t 在 s 中的所有位置（允许重叠）
	indexAll := func(s, t []byte) []int {
		pos := suffixarray.New(s).Lookup(t, -1)
		sort.Ints(pos)
		return pos
	}

	// 字符串哈希 rolling hash, Rabin–Karp algorithm
	// https://en.wikipedia.org/wiki/Hash_function
	// https://en.wikipedia.org/wiki/Rolling_hash
	// https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
	// 线性同余方法（LCG）https://en.wikipedia.org/wiki/Linear_congruential_generator
	// https://oi-wiki.org/string/hash/
	// 利用 set 可以求出固定长度的不同子串个数
	// todo 浅谈字符串 hash 的应用 https://www.luogu.com.cn/blog/Flying2018/qian-tan-zi-fu-chuan-hash
	//      anti-hash: 最好不要自然溢出 https://codeforces.com/blog/entry/4898
	//      On the mathematics behind rolling hashes and anti-hash tests https://codeforces.com/blog/entry/60442
	//      hash killer https://loj.ac/p/6758
	// 题目推荐 https://cp-algorithms.com/string/string-hashing.html#toc-tgt-7
	// 模板题 https://www.luogu.com.cn/problem/P3370
	// LC187 找出所有重复出现的长为 10 的子串 https://leetcode-cn.com/problems/repeated-dna-sequences/
	// LC1044 最长重复子串（二分哈希）https://leetcode-cn.com/problems/longest-duplicate-substring/
	// LC1554 只有一个不同字符的字符串 https://leetcode-cn.com/problems/strings-differ-by-one-character/
	hash := func(s []byte) {
		// 注意：由于哈希很容易被卡，能用其它方法实现尽量用其它方法
		const prime uint64 = 1e8 + 7
		powP := make([]uint64, len(s)+1) // powP[i] = prime^i
		powP[0] = 1
		preHash := make([]uint64, len(s)+1) // preHash[i] = hash(s[:i])
		for i, b := range s {
			powP[i+1] = powP[i] * prime
			preHash[i+1] = preHash[i]*prime + uint64(b)
		}

		// 计算子串 s[l:r] 的哈希
		subHash := func(l, r int) uint64 { return preHash[r] - preHash[l]*powP[r-l] }
		_ = subHash
	}

	// KMP (Knuth–Morris–Pratt algorithm)