package main

import (
	"fmt"
)

func main() {
	text := "AYRRQMGRPCRQ"
	subStr := "RPCRQ"
	fmt.Printf("text = %+v\n", text)
	fmt.Printf("subStr = %+v\n", subStr)

	// 構(gòu)建子字符串中各個(gè)字符及相應(yīng)的索引的映射
	m := make(map[byte]int, len(subStr))
	for i := 0; i < len(subStr); i ++ {
		m[subStr[i]] = i
	}
	fmt.Printf("m = %+v\n", m)

	shiftLength := 0
	subIndex := len(subStr) - 1
	for shiftLength <= len(text) - len(subStr) {
		// 每次比較都從子字符串的末尾開始向前，逐個(gè)字符進(jìn)行比較
		for subIndex >= 0 && text[shiftLength + subIndex] == subStr[subIndex] {
			subIndex --
		}

		if subIndex == -1 {
			// 子字符串在文本中出現(xiàn)，跳過文本中的子字符串繼續(xù)向后查找
			fmt.Printf("subStr found in text at index %+v\n", shiftLength)
			shiftLength += len(subStr)
		} else if v, ok := m[text[shiftLength + subIndex]]; ok {
			// 文本中的字符與子字符串中相應(yīng)位置的字符不匹配，但該字符在子字符串中存在
			if subIndex > v {
				// 如果該字符在子字符串中的位置在當(dāng)前索引位置之前，則將二者位置對齊，然后重新查找
				shiftLength += subIndex - v
			} else {
				// 文本中的索引位置向前移動一個(gè)字符（考慮子字符串中同一個(gè)字符重復(fù)出現(xiàn)的情況）
				shiftLength += 1
			}
		} else {
			// 文本中的字符在子字符串中不存在
			shiftLength += subIndex
		}

		subIndex = len(subStr) - 1
	}
}

package main

import (
	"fmt"
)

func main() {
	text := "AYCRQMGRQCRQ"
	subStr := "RQCRQ"
	fmt.Printf("text = %+v\n", text)
	fmt.Printf("subStr = %+v\n", subStr)

	shifts := make([]int, len(subStr) + 1)
	borderPosition := make([]int, len(subStr) + 1)

	// 確定搜索字符串中各個(gè)子串的邊界
	i, j := len(subStr), len(subStr) + 1
	borderPosition[i] = j

	for i > 0 {
		for j >= 0 && j <= len(subStr) && subStr[i - 1] != subStr[j - 1] {
			if shifts[j] == 0 {
				shifts[j] = j - i
			}

			j = borderPosition[j]
		}

		i --
		j --
		borderPosition[i] = j
	}

	fmt.Printf("shifts = %+v\n", shifts)
	fmt.Printf("borderPosition = %+v\n", borderPosition)

	// 確定搜索字符串中各個(gè)字符與文本中的字符不匹配時(shí)應(yīng)該移動的距離
	j = borderPosition[0]
	for i := 0; i <= len(subStr); i ++ {
		if shifts[i] == 0 {
			shifts[i] = j
		}

		if i == j {
			j = borderPosition[j]
		}
	}

	fmt.Printf("shifts = %+v\n", shifts)
	fmt.Printf("borderPosition = %+v\n", borderPosition)

	// 在文本中搜索字符串
	shiftLength := 0
	for shiftLength <= len(text) - len(subStr) {
		j = len(subStr) - 1
		for j >= 0 && subStr[j] == text[shiftLength + j] {
			j --
		}

		if j == -1 {
			fmt.Printf("subStr find in text at position %+v\n", shiftLength)
			shiftLength += shifts[0]
		} else {
			shiftLength += shifts[j + 1]
		}
	}
}