// 选择非常大的一个质数16777619 作为 base 
const primeRK = 16777619   

// hashStr 返回子串的hash值和乘数因子
func hashStr(sep string) (uint32, uint32) {
	hash := uint32(0)
	for i := 0; i < len(sep); i++ {
		hash = hash*primeRK + uint32(sep[i])  //计算hash值
	}
    // 计算(最高位 + 1)位的乘数因子, 使用位移, 没有使用 i--, 可以有效减少循环次数. i >>=1 相当于遍历二进制的每一位
	var pow, sq uint32 = 1, primeRK
	for i := len(sep); i > 0; i >>= 1 {
		if i&1 != 0 {
			pow *= sq
		}
		sq *= sq
	}
	return hash, pow
}

// Index 返回sep在s里第一次匹配时的index, 无法匹配则返回-1.
func Index(s, sep string) int {
	n := len(sep)
    // 先分析一些常见情况, 起到进一步加速的效果
	switch {   
	case n == 0:
		return 0
	case n == 1:  //如果为一个字节,则调用IndixByte(汇编语言)
		return IndexByte(s, sep[0])
	case n <= shortStringLen:  //如果sep的长度小于31且大于1, 则使用汇编代码(也是一种优化). 
		return indexShortStr(s, sep)  
	case n == len(s):  
		if sep == s {
			return 0
		}
		return -1
	case n > len(s):
		return -1
	}
	// 使用Rabin-Karp算法匹配
    // 步骤1 初始计算待匹配的文本的hash值和乘数因子, 
	hashsep, pow := hashStr(sep)
	var h uint32
	for i := 0; i < n; i++ {
		h = h*primeRK + uint32(s[i])  // 步骤2 计算长度跟sep一样的s子串的hash值
	}
	if h == hashsep && s[:n] == sep {
		return 0
	}
	for i := n; i < len(s); {
        // 利用先前的hash值, 计算新的hash值 
		h *= primeRK  // 乘以base
		h += uint32(s[i]) // 加上下一个字符的 hash 值
		h -= pow * uint32(s[i-n]) // 减去先前子串的第一个字符的hash值
		i++
        // 如果hash相等则继续使用朴素算法比较, 如果hash不一致,则直接用下一个匹配
		if h == hashsep && s[i-n:i] == sep {   
			return i - n
		}
	}
	return -1
}

func makeStringFinder(pattern string) *stringFinder {
	f := &stringFinder{
		pattern:        pattern,
		goodSuffixSkip: make([]int, len(pattern)),
	}
	// last 是pattern最后一个字符的索引
	last := len(pattern) - 1

	// 创建坏字符表，记录不匹配时T的i指针移动步数
	// 第一阶段，初始化256个字符全部移动 len(pattern) 步
	for i := range f.badCharSkip {
		f.badCharSkip[i] = len(pattern)
	}

	// 第二阶段：从左到右遍历pattern，更新其索引与P末尾的距离，结果就是该字符到末尾的最小距离
	// 没有计算last byte的距离, 因为移动至少要一步。 没有0步。 
	for i := 0; i < last; i++ {
		f.badCharSkip[pattern[i]] = last - i
	}

	// 创建好后缀表
	// 第一阶段: 此时pattern[i+1:]都是已经匹配的，且好后缀只出现了一次
	// 计算T中的指针要移动的步数
	lastPrefix := last
	for i := last; i >= 0; i-- {
		if HasPrefix(pattern, pattern[i+1:]) {
			lastPrefix = i + 1
		}
		// 好后缀时T的指针移动分两步，首先移动到与 pattern的末尾对齐，即 last - i
		// lastPrefix 用来记录 pattern[i+1:]中所有后缀与同等长度的前缀相等时的最大索引
		// 然后移动 lastPrefix步
		f.goodSuffixSkip[i] = lastPrefix + last - i
	}
	// 第二阶段: 好后缀在pattern前面部分还出现过, 如下计算相应的移动步数
	// 会覆盖之前第一阶段的部分值。但好后缀出现过移动步数比没出现的小。所以最终值是正确的
	// 举例： "mississi" 中好后缀是issi, 在pattern[1]处出现过，所以移动步数为 last-i  +  lenSuffix
	for i := 0; i < last; i++ {
		lenSuffix := longestCommonSuffix(pattern, pattern[1:i+1])
		if pattern[i-lenSuffix] != pattern[last-lenSuffix] {
			// (last-i) is the shift, and lenSuffix is len(suffix).
			f.goodSuffixSkip[last-lenSuffix] = lenSuffix + last - i
		}
	}
	return f
}
// longestCommonSuffix 仅仅比较两个字符串的共同后缀的长度, 没有则为0
func longestCommonSuffix(a, b string) (i int) {
	for ; i < len(a) && i < len(b); i++ {
		if a[len(a)-1-i] != b[len(b)-1-i] {
			break
		}
	}
	return
}

// next 主要返回p在text里第一次匹配时的索引, 不匹配则返回-1
func (f *stringFinder) next(text string) int {
    // i 是T(即变量text)中要检查的字符索引, j为P中要检查的字符索引

    // 因从后向前比较, 所以i初始化为P的最后一位索引
	i := len(f.pattern) - 1
	for i < len(text) {
        // 每次比较时都从p的最后一位开始比较
		j := len(f.pattern) - 1
		for j >= 0 && text[i] == f.pattern[j] {
			i--
			j--
		}
        // j为负数,说明匹配成功, 则直接返回 i+ 1 
		if j < 0 {
			return i + 1
		}
        // j为非负, 表明text[i] != f.pattern[j], 则从坏字符表和好后缀表中获取分别获取i需要移动的步数, 取最大值并使移动到新位置
		i += max(f.badCharSkip[text[i]], f.goodSuffixSkip[j])
	}
	return -1
}