// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// rabinKarpSearch 函数接受两个字符串输入：文本和模式
func rabinKarpSearch(text string, pattern string) int {
	// 计算文本和模式的长度
	n := len(text)
	m := len(pattern)

	// 如果模式比文本长，则找不到模式
	if n < m {
		return -1
	}

	// 设置一个质数和一个幂变量
	prime := 101
	power := 1

	// 计算模式的哈希值和文本的第1个窗口
	hpattern := 0
	htext := 0
	for i := 0; i < m; i++ {
		hpattern = (hpattern*prime + int(pattern[i])) % prime
		htext = (htext*prime + int(text[i])) % prime
	}

	// 计算素数^(m-1)的幂
	for i := 0; i < m-1; i++ {
		power = (power * prime) % prime
	}

	// 将模式滑过文本并检查匹配
	for i := 0; i <= n-m; i++ {
		// 如果模式和文本的哈希值匹配，则检查是否完全匹配
		if hpattern == htext {
			match := true
			for j := 0; j < m; j++ {
				if pattern[j] != text[i+j] {
					match = false
					break
				}
			}
			if match {
				return i
			}
		}
		// 为下一次迭代更新文本窗口的哈希值
		if i < n-m {
			htext = (prime*(htext-int(text[i])*power) + int(text[i+m])) % prime
			if htext < 0 {
				htext += prime
			}
		}
	}

	// 在文本中找不到该模式
	return -1
}

func main() {
	// 定义要搜索的文本和模式
	text := "I love Go algorithms, this is an example"
	pattern := "love"

	// 调用 rabinKarpSearch 函数在文本中查找模式
	index := rabinKarpSearch(text, pattern)

	// 打印结果
	if index == -1 {
		fmt.Println("在文本中找不到模式")
	} else {
		fmt.Printf("在文本中的索引 %d 处找到模式\n", index)
	}
}

//$ go run rabinKarpSearch.go
//在文本中的索引 2 处找到模式