对于某个字符串 "abcdefaaa" ... 那么想对他进行编码 怎么编?

abcde这些映射为整数 01234 ...

假设有个idx数组 映射的整数则是idx[s[i]]

这个base一定是一个素数 作为基数 防止hash冲突

那么有:hash[i]=h a s h[i-1] * b a s e+i d x[s[i]]

根据这个定义 我们对字符串S=s_1 s_2 s_3 s_4 s_5 求hash[s_1] 和s_2都是字符对应的值

h a s h[0]=0 前 0 个字符串 默认直接是 0

h a s h[1]=s_1 前1个字符串 就是s_1 本身

h a s h[2]=s_1 * base + s_2

h a s h[3]=s_1 * b a s e^2+s_2 * b a s e+s_3

h a s h[4]=s_1 * b a s e^3+s_2 * b a s e^2+s_3 * b a s e+s_4

h a s h[5]=s_1 * b a s e^4+s_2 * b a s e^3+s_3 * b a s e^2+s_4 * b a s e+s_5

那s_3 s_4 的hash值按定义应该是s_3 * b a s e+s_4

那可以发现hash[4]-hash[2]*{ base }^2=s_3 * b a s e+s_4

因此总结公式:

S=s_1 s_2 \ldots s_n 字符串的hash值其子串s_l \ldots s_r 对应的hash值为:

可以对hash值取mod

如果需要反复对子串求解hash值，预处理base^n 效果更佳。所以才有上面用p[i]=b a s e^i \% M O D ，也是有取余数的。

	hash := make([]int64, len(s)+1) // hash直接为数组 表示前缀的hash值
	base := make([]int64, len(s)+1) // 这个数组 i下标表示Prime的i次方
	base[0] = 1
	hash[0] = 0 //  前0个hash就直接为0
	// 维护hash的前缀
	for i := 1; i <= len(s); i++ {
		hash[i] = (hash[i-1]*Prime + int64(s[i-1])) 
		base[i] = (base[i-1] * Prime)  // 记录次方
	}
	res := make([]string, 0)
	mp := make(map[int64]int) // 记录结果的map
    // 表示从第i个字符到第j个字符 i>=1
    // 实际的字符串应该是 i-1 :i+L-1
	for i := 1; i <= len(s)-L+1; i++ {
		//起始i 结束则是i+L-1
		j := i + L -1
		// 取出i到j的hash值
		hash := hash[j] - hash[i-1]*base[j-i+1]  // 做减法可能变负数了 因此再加个mod再去余
		mp[hash]++
		if mp[hash] == 2 {
			res = append(res, s[i-1:i+L-1])
		}
	}
	return res
}