约瑟夫环+链表+字符串

约瑟夫环问题

介绍

约瑟夫问题的源头完全可以命名为“自杀游戏”，换言之“丢手绢”。问题描述如下：

现有n个人围成一桌坐下，编号从1到n，从编号为1的人开始报数。报数也从1开始，报到m的人离席，从离席者的下一位在座成员开始，继续从1开始报数。复现这个过程（各成员的离席次序），或者求最后一个在座的成员编号。

数组方法

不断对数组进行遍历，不断统计叫号的数i，当i达到m，该人出局，将报数出局的人做标记-1，直到剩下一个非-1的。

麻烦的点在于会不断遍历到已经出局的人，每次都要遍历-1的元素。

func josephArray(n, m int) int {
	ring := make([]int, n) //初始化n个人的环数组
	count, k := 0, -1      //count记录报数的人,k用来遍历
	for count < n-1 {
		i := 0      //统计叫号
		for i < m { //模拟一轮叫号
			k = (k + 1) % n
			if ring[k] == 0 { //还没有出局就要叫号
				i++
				if i == m { //叫号是m就要出局
					ring[k] = -1
					count++
				}
			}
		}
	}
	//找到幸存者
	for i := 0; i < n; i++ {
		if ring[i] == 0 {
			fmt.Println("saver:", i+1)
			return i + 1
			break
		}
	}
	return 0
}

循环链表

type Node struct {
	Value int
	Next  *Node
}

func CreateCircularLinkList(n int) (*Node, *Node) {
	if n < 1 {
		return nil, nil
	}

	//初始化头指针和当前节点
	head := &Node{Value: 1}
	cur := head
	//创建剩余n-1个结点
	for i := 2; i <= n; i++ {
		newNode := &Node{Value: i}
		cur.Next = newNode
		cur = newNode
	}
	//尾指向头，成环
	cur.Next = head
	return cur, head
}

func josephLinkList(n, m int) int {
	//创建环,获取头尾指针
	prev, head := CreateCircularLinkList(n)

	for head != head.Next {
		//模拟一轮删除
		for i := 0; i < m-1; i++ {
			prev = head
			head = head.Next
		}
		fmt.Printf("淘汰节点: %d\n", head.Value)
		prev.Next = head.Next
		head = prev.Next
	}
	fmt.Println("saver:", head.Value)
	return head.Value
}

递归

每次出局后就对剩余的人重新编号，然后开始新一轮淘汰。
比较困难的是解决父问题到子问题的映射关系,模拟过程领悟一下。。。
从1开始编码，临界为f(1,m)=1,建立f(n-1,m)–>f(n,m)的映射关系，f(n, m) = (f(n - 1, m) + m - 1) % n + 1
因为不允许编码0出现，保证至少是1，所以上述取余前减一，取余后加一，
但如果从0开始编码，那么f(0,m)=0，f(n, m) = (f(n - 1, m) + m) % n

func JosephRec(n, m int) int {
	if n == 1 {
		return n
	}
	return (JosephRec(n-1, m)+m-1)%n + 1
}

链表

解决链表问题要时刻小心访问空指针，一定要检查好指针情况。

对边界条件的检查也很重要，比如头和尾的检查

1.移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

移除链表元素主要涉及链表的删除，比较简单，需要重点掌握利用空的头结点来简化问题的方法。

直接删除

直接删除需要考虑头结点和普通节点两种不同的处理方法

func removeElements(head *ListNode, val int) *ListNode {
	//头结点特殊处理
	for head != nil && head.Val == val {
		head = head.Next
	}
	//链表为空特殊处理
	if head == nil {
		return head
	}
	//普通结点处理
	prev := head
	for prev.Next != nil {//要访问prev.Next所以确保非空
		if prev.Next.Val == val {
			prev.Next = prev.Next.Next
		} else {
			prev = prev.Next
		}
	}
	return head
}

虚拟头结点

创建一个虚拟的头结点，使得原先不带头结点的链表转变为带头结点的链表，这样链表就有了前置的空结点，就将头结点一般化为普通节点。因此就不用忧虑原先的删除头结点的问题了，和处理一般结点的做法是一样的。

func removeElements1(head *ListNode, val int) *ListNode {
	//虚拟一个空的头结点
	newHead := new(ListNode)
	newHead.Next = head
	prev := newHead
	for head != nil {
		if head.Val == val {//删除对应值的结点
			prev.Next = head.Next
			head = prev.Next
		} else {//继续遍历
			head = head.Next
			prev = prev.Next
		}
	}
	return newHead.Next
}

递归

递归就是边界+问题分解+处理当前问题

func removeElements2(head *ListNode, val int) *ListNode {
	// 边界，递归结束条件
	if head == nil {
		return nil
	}
	// 递归处理后续链表
	head.Next = removeElements2(head.Next, val)
	// 处理当前结点的逻辑
	if head.Val == val {
		return head.Next
	} else {
		return head
	}
}

2.设计链表

太久没做了有点生疏了，对问题的思考不到位导致卡了很长时间，其实不难。这道题的下标是从0开始的，而以前学的是从1开始的，所以在实现上略有差别，但是无伤大雅。

关键：对于边界情况的检查尽量都交给链表结点的检查，也就是检查结点非空或结点Next非空，这样对于思路比较统一（以前学的这一套）

type MyLinkedList struct {
	val  int
	next *MyLinkedList
}

func Constructor() MyLinkedList {
	obj := new(MyLinkedList)
	obj.val = 0
	obj.next = nil
	return *obj
}

// 找到索引对应的结点
func (this *MyLinkedList) Get(index int) int {
	//处理临界：索引不合法或链表为空
	if index < 0 || this.next == nil {
		return -1
	}
	//从索引0对应结点开始找到要求索引的结点
	node := this.next
	for i := 0; i < index; i++ {
		//结点为空就返回-1
		if node == nil {
			return -1
		}
		//继续遍历
		node = node.next
	}
	if node != nil {
		return node.val
	}
	return -1
}

func (this *MyLinkedList) AddAtHead(val int) {
	node := new(MyLinkedList)
	node.val = val

	node.next = this.next
	this.next = node
}

func (this *MyLinkedList) AddAtTail(val int) {
	//创建节点
	node := new(MyLinkedList)
	node.val = val
	node.next = nil
	//寻找尾结点
	tail := this //如果链表为空，this.next为nil，不能访问空指针，要从头结点开始遍历
	for tail.next != nil {
		tail = tail.next
	}

	tail.next = node
}

/*
index从0开始
将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
如果 index 比长度更大，该节点将 不会插入 到链表中。
*/
func (this *MyLinkedList) AddAtIndex(index int, val int) {
	//index<0
	if index < 0 {
		return
	}
	//寻找插入点,如果 index 比长度更大，该节点将 不会插入 到链表中
	count := 0
	prev := this
	// for prev.next != nil && count < index { //prev最多指向最后一个结点
	// 	prev = prev.next
	// 	count++
	// }
	// if count != index { //因为 prev.next==nil也是允许插入结点的情况，所以只能根据下标情况来判断合不合法了（以前学的写法和这个不太一样，主要原因是索引起始值）
	// 	return
	// }
	for prev != nil && count < index {
		prev = prev.next
		count++
	}
	if prev == nil {
		return
	}

	//创建节点
	node := new(MyLinkedList)
	node.val = val
	node.next = nil

	//插入
	node.next = prev.next
	prev.next = node

}

// 如果下标有效，则删除链表中下标为 index 的节点
func (this *MyLinkedList) DeleteAtIndex(index int) {
	//非法index或空链表要返回
	if index < 0 || this.next == nil {
		return
	}
	//寻找删除点
	prev := this
	count := 0
	for prev.next != nil && count < index {
		count++
		prev = prev.next
	}
	//没找到要删除的结点
	if prev.next == nil {
		return
	}
	//找到要删除的结点，执行删除操作
	prev.next = prev.next.next
	// if count == index && prev.next != nil {
	// 	prev.next = prev.next.next
	// }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Get(index);
 * obj.AddAtHead(val);
 * obj.AddAtTail(val);
 * obj.AddAtIndex(index,val);
 * obj.DeleteAtIndex(index);
 */

3.反转链表

双指针

一个指针指向反转好的链表的头结点pre，一个指针指向待反转的链表的头结点cur，还有个指针记录下一个结点方便cur移动，不断反转。

func reverseList(head *ListNode) *ListNode {
	var pre *ListNode //pre指向新链表的第一个结点
	cur := head       //cur指向待反转的链表
	for cur != nil {
		nex := cur.Next
		cur.Next = pre
		pre = cur
		cur = nex
	}
	return pre
}

递归

递归思路比双指针的迭代难想一点

4.两两交换链表中的节点

虚拟头结点的极致运用，一般化头两个结点的处理方式。cur永远指向需要交换的两个结点的前一个结点.

强调for循环的检查条件

func swapPairs(head *ListNode) *ListNode {
	dummyHead := &ListNode{0, head}
	cur := dummyHead //指针类型
	for cur.Next != nil && cur.Next.Next != nil {
		//node1和node2对应需要两两交换的结点
		node1 := cur.Next
		node2 := cur.Next.Next
		//交换
		node1.Next = node2.Next
		node2.Next = node1
		//更新cur
		cur.Next = node2
		cur = node1
	}
	return dummyHead.Next
}

5.删除链表的倒数第N个节点

快慢指针方法的运用，先让快指针先走n步，如果fast为空则删除头结点。再同时让两个指针一起移动，直到快指针Next为空，删除Slow.Next

//双指针，先让快指针先走n步，如果fast为空则删除头结点。再同时让两个指针一起移动，直到快指针Next为空，删除Slow.Next
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	slow, fast := head, head
	// 先让快指针先走n步
	for i := 0; i < n; i++ {
		fast = fast.Next
	}
	//fast遍历到尾,说明删除的是头指针
	if fast == nil {
		return head.Next
	}
	//快慢指针一起移动，直到快指针next为空
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	//删除指定结点
	slow.Next = slow.Next.Next
	return head
}

6.链表相交

求相交起始点，关键在于处理遍历长度的问题，要保证遍历时两个指针到链表尾的距离相等，这样才能发现相交

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	//获取链表A、B的长度
	pa, pb := headA, headB
	lenA, lenB := 0, 0
	for pa != nil {
		lenA++
		pa = pa.Next
	}
	for pb != nil {
		lenB++
		pb = pb.Next
	}
	// 让curA始终是长度较长的链表
	curA := headA
	curB := headB
	if lenA < lenB {
		curA, curB = headB, headA
		lenA, lenB = lenB, lenA
	}
	//将curA和curB长度对齐
	for lenA != lenB {
		curA = curA.Next
		lenA--
	}
	//同时遍历curA和curB，求相交，遍历条件是curA不为空，链表的遍历很多时候都要求非空
	for curA != nil {
		if curA == curB {
			return curA
		}
		curA = curA.Next
		curB = curB.Next
	}
	return nil
}

// a+b的长度是一样的，遍历a+b来确认相交点
func getIntersectionNode1(headA, headB *ListNode) *ListNode {
	//优先处理链表为空情况
	if headA == nil || headB == nil {
		return nil
	}
	//遍历两个链表之和以平衡指针起始位置不同的问题
	pa, pb := headA, headB
	for pa != pb { //如果有相交会相等，没有相交最后为空也会退出
		//指针为空说明遍历完a了，接下来遍历b
		if pa != nil {
			pa = pa.Next
		} else {
			pa = headB
		}

		if pb != nil {
			pb = pb.Next
		} else {
			pb = headA
		}
	}
	return pa
}

7.环形链表

一道需要数学推导的快慢指针方法的链表题

func detectCycle(head *ListNode) *ListNode {
	//快慢指针
	slow, fast := head, head
	//快慢指针相遇
	for fast != nil && fast.Next != nil { //确保不访问空指针
		fast = fast.Next.Next
		slow = slow.Next
		//相遇求环入口
		if fast == slow {
			p := head
			for p != slow {
				p = p.Next
				slow = slow.Next
			}
			return p
		}
	}
	//无环返回空
	return nil
}

字符串

知识点

在 Go 语言 中，字符串是重要的基础数据类型，且具备一些独特的特性。以下是 Golang 字符串相关知识点的详细总结：

---

1. 字符串的基本特性

1. 不可变：Go 中的字符串是 只读的字节序列，一旦创建无法修改。
2. UTF-8 编码：Go 默认使用 UTF-8 编码，支持中文、Emoji 等多字节字符。
3. 字符串是字节序列：可以通过 []byte 或 []rune 将字符串拆分处理。

---

2. 常用字符串操作（strings 包）

strings 包提供了一系列用于处理字符串的函数。

1️⃣ 查找和判断

• **strings.Contains(s, substr)**：检查 s 是否包含 substr。

  strings.Contains("golang", "go")  // true

• **strings.HasPrefix(s, prefix)**：判断 s 是否以 prefix 开头。

  strings.HasPrefix("hello", "he")  // true

• **strings.HasSuffix(s, suffix)**：判断 s 是否以 suffix 结尾。

  strings.HasSuffix("hello", "lo")  // true

• **strings.Index(s, substr)**：返回 substr 在 s 中的第一次出现位置（找不到则返回 -1）。

  strings.Index("golang", "go")  // 0

---

2️⃣ 字符串修改

• **strings.ReplaceAll(s, old, new)**：替换字符串中的所有 old 为 new。

  strings.ReplaceAll("hello world", "o", "0")  // "hell0 w0rld"

• **strings.Trim(s, cutset)**：去除字符串两端的指定字符。

  strings.Trim("!!hello!!", "!")  // "hello"

• **strings.TrimSpace(s)**：去除字符串两端的空白字符。

  strings.TrimSpace("  hello  ")  // "hello"

---

3️⃣ 分割与拼接

• **strings.Split(s, sep)**：按指定分隔符将字符串分割成切片。

  strings.Split("a,b,c", ",")  // ["a", "b", "c"]

• **strings.Join(slice, sep)**：将字符串切片拼接成一个字符串。

  strings.Join([]string{"a", "b", "c"}, ",")  // "a,b,c"

---

4️⃣ 大小写转换

• **strings.ToUpper(s)**：将字符串转换为大写。

  strings.ToUpper("hello")  // "HELLO"

• **strings.ToLower(s)**：将字符串转换为小写。

  strings.ToLower("HELLO")  // "hello"

---

3. 字符串与其他类型转换

1️⃣ 字符串与字节切片转换

• **[]byte**：将字符串转换为字节切片。

  b := []byte("hello")  // [104 101 108 108 111]

• **string()**：将字节切片转换为字符串。

  s := string([]byte{104, 101, 108, 108, 111})  // "hello"

2️⃣ 字符串与 rune 切片转换

• **[]rune**：支持多字节字符的转换（如中文）。

  r := []rune("你好")  // [20320 22909]

---

4. 遍历字符串

1️⃣ 按字节遍历

s := "Hello"
for i := 0; i < len(s); i++ {
    fmt.Printf("%c ", s[i])  // H e l l o
}

2️⃣ 按字符（rune）遍历

s := "你好"
for _, r := range s {
    fmt.Printf("%c ", r)  // 你 好
}

---

5. 字符串格式化 (fmt 包)

• **fmt.Sprintf()**：格式化字符串。

  name := "Alice"
  age := 25
  msg := fmt.Sprintf("Name: %s, Age: %d", name, age)
  fmt.Println(msg)  // "Name: Alice, Age: 25"

---

6. 常见面试陷阱与注意点

1. 字符串拼接性能：
   频繁拼接字符串时，用 strings.Builder 比直接 + 高效。

   var builder strings.Builder
   builder.WriteString("Hello")
   builder.WriteString(" World")
   fmt.Println(builder.String())  // "Hello World"

2. 空字符串与 nil 区别：
   字符串变量默认值是 **""**（而不是 nil）。

3. 字符与字符串的区别：

   • **byte**：单个 ASCII 字符
   • **rune**：单个 Unicode 字符

---

7. 字符串反转的实现

Go 语言没有内置的字符串反转函数，可以参考以下实现：

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

---

8. 常用的字符串包函数速查表

函数	描述
Contains	判断是否包含子串
HasPrefix / HasSuffix	判断前缀或后缀
Index	返回子串的索引
ReplaceAll	替换所有匹配子串
Split / Join	分割与拼接字符串
ToUpper / ToLower	大小写转换
Trim / TrimSpace	去除字符或空白

---

总结

• 不可变性：Go 中字符串不可变，适合用于多线程场景。
• UTF-8 支持：天然支持中文、Emoji 等多字节字符。
• 性能：频繁拼接字符串建议使用 **strings.Builder**。
• 遍历技巧：需要按字符处理时使用 **rune**。

熟练掌握 strings 包的函数和相关技巧，可以让你在日常开发中处理字符串更加高效。

strings包

Go语言中的 strings 包提供了多种字符串操作函数，涵盖了常见的字符串处理需求。下面是该包中重要函数及其用法总结，让你快速掌握。

---

1️⃣ 基本字符串查找和判断

函数	描述	示例
Contains(s, substr string)	判断 s 中是否包含 substr	strings.Contains("hello", "ll") // true
ContainsAny(s, chars string)	判断 s 是否包含 chars 中的任意字符	strings.ContainsAny("team", "ae") // true
HasPrefix(s, prefix string)	判断 s 是否以 prefix 开头	strings.HasPrefix("golang", "go") // true
HasSuffix(s, suffix string)	判断 s 是否以 suffix 结尾	strings.HasSuffix("golang", "lang") // true
Index(s, substr string)	返回 substr 在 s 中的第一个索引位置（若不存在返回 -1）	strings.Index("chocolate", "o") // 2
LastIndex(s, substr string)	返回 substr 在 s 中的最后一个索引位置	strings.LastIndex("go gopher", "go") // 3

---

2️⃣ 字符串替换与拆分

函数	描述	示例
Replace(s, old, new string, n int)	将 s 中前 n 个 old 替换为 new	strings.Replace("apple apple", "apple", "orange", 1) // "orange apple"
ReplaceAll(s, old, new string)	替换所有匹配的子串	strings.ReplaceAll("foo bar foo", "foo", "baz") // "baz bar baz"
Split(s, sep string)	根据 sep 拆分字符串，返回切片	strings.Split("a,b,c", ",") // ["a" "b" "c"]
SplitN(s, sep string, n int)	拆分成最多 n 部分	strings.SplitN("a,b,c", ",", 2) // ["a" "b,c"]
Join(elems []string, sep string)	使用 sep 将字符串切片连接起来	strings.Join([]string{"a", "b", "c"}, ",") // "a,b,c"

---

3️⃣ 大小写转换

函数	描述	示例
ToUpper(s string)	将字符串转换为大写	strings.ToUpper("hello") // "HELLO"
ToLower(s string)	将字符串转换为小写	strings.ToLower("WORLD") // "world"
ToTitle(s string)	将每个单词首字母大写	strings.ToTitle("hello world") // "HELLO WORLD"

---

4️⃣ 去除空格与其他字符

函数	描述	示例
Trim(s, cutset string)	去除 s 两端的指定字符	strings.Trim("!!!hello!!!", "!") // "hello"
TrimSpace(s string)	去除字符串两端的空格	strings.TrimSpace(" hello ") // "hello"
TrimPrefix(s, prefix string)	去除前缀（若存在）	strings.TrimPrefix("prefix-abc", "prefix-") // "abc"
TrimSuffix(s, suffix string)	去除后缀（若存在）	strings.TrimSuffix("file.txt", ".txt") // "file"

---

5️⃣ 字符串重复、计数、生成

函数	描述	示例
Repeat(s string, count int)	返回 s 重复 count 次的结果	strings.Repeat("go", 3) // "gogogo"
Count(s, substr string)	返回子串在字符串中出现的次数	strings.Count("cheese", "e") // 3
Fields(s string)	根据空白字符拆分成字符串切片	strings.Fields("foo bar") // ["foo" "bar"]

---

6️⃣ 字符串比较

函数	描述	示例
Compare(a, b string)	按字典序比较两个字符串，返回 -1、0 或 1	strings.Compare("a", "b") // -1
EqualFold(s1, s2 string)	忽略大小写比较两个字符串是否相等	strings.EqualFold("Go", "go") // true

---

7️⃣ 示例：实际应用代码

package main

import (
    "fmt"
    "strings"
)

func main() {
    // 判断子串
    s := "hello world"
    fmt.Println(strings.Contains(s, "world")) // true

    // 拆分与连接
    parts := strings.Split(s, " ")
    fmt.Println(parts)                        // ["hello", "world"]
    joined := strings.Join(parts, "-")
    fmt.Println(joined)                       // "hello-world"

    // 字符串替换
    fmt.Println(strings.ReplaceAll(s, "l", "x")) // "hexxo worxd"

    // 大小写转换
    fmt.Println(strings.ToUpper(s)) // "HELLO WORLD"

    // 去除空格
    fmt.Println(strings.TrimSpace("  hello  ")) // "hello"
}

---

总结：

strings 包功能全面，涵盖了查找、拆分、连接、替换、去除空格等操作。在实际开发中，合理使用这些函数可以大大简化字符串的处理逻辑。如果你对某个函数的细节还有疑问，请随时问我！

KMP算法

1. 作用

   KMP减少了匹配时指针的回溯，加速了匹配过程

   KMP算法有点像人眼优化BF算法，利用已经部分匹配这个有效信息，保持i指针不回溯；通过修改j指针，让模式串尽量地移动到有效的位置。

   当匹配失败时，j要移动的下一个位置k，存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。如果用数学公式来表示是这样的：P[0 ~ k-1] == P[j-k ~ j-1]

2. next数组：指的是当主串和模式串失配的时候，指向模式串的指针要指向的下一个位置。利用P[0 ~ k-1] == P[j-k ~ j-1]性质求取next数组，

3. getNext函数

   • j和k的实际作用：

     j的作用：指向需计算next值的那个字符x的前面子串的末尾，以及下一次指向x；

     K的作用：指向最大相等前缀的末尾后面那个字符（也就是最大相等前缀的长度）；

   • 初始时为什么是k=-1，next[0]=-1？

     为了表示初始情况没有前缀是匹配的，j指针不能再往前回退了，j指针应该后移进行新一轮的匹配。

   • 为什么是k==-1 || t.ch[j]==t.ch[k] ？

     k=-1表示没有前缀是匹配的，t.ch[j]==t.ch[k]表示当前字符匹配，它们都指明了next[j+1]的数值。k=-1时，next[j+1]=0，表示出现j+1位不匹配时j回溯到0，也就是从头开始匹配；t.ch[j]==t.ch[k]时next[j+1]=k+1，第j+1位的前k位和模式串前k位相等，表示j+1位出现不匹配时j指针回溯到k+1。

   • t.ch[j]==t.ch[k]怎么推出t.ch[j+1]=k+1的？

     因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）这时候现有P[k] == P[j]，我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1。这和j的作用是相契合的，j指向需计算next值的那个字符x的前面子串的末尾，计算next数组时自然要更新next[j+1]。

   • 为什么k=next[k]？

     因为模式串的前缀和后缀之间存在相同的部分，充分利用已经得到的匹配消息，减少不必要的匹配。因此，k = next[k] 的作用就是：找到当前已经匹配部分的最长相同前缀对应的位置，从那里重新开始比较

   • 改进的核心思想：

     按原始的GetNext求法，如果将来比较时，主串的字符x和这里 j 处的不相等，那么子串将回退到 k 号字符来和 x 比较。但是，如果 j 号字符和 k号字符是一样的，那么意味着，k号字符也不等于x啊！所以在此情况下，KMP 仅回退到 k 号字符是没用的，因为必然还得再回退到 k号字符 对应的next 值，即 next [k] 处。因此，与其等KMP折腾，不如在建立next函数时，就把这种事考虑好，直接next[j]=next[k]，一次到位得了。

4. strStr

   实现思路和getNext是非常相近的：

   定义i和j两个指针，分别指向主串和子串。

   首先获取next数组，在字符串长度以内进行遍历，如果j==-1（j回溯到头了，下一次要从0开始再比较）或者主串和子串对应字符匹配（需要继续比较下一个字符），i和j都往后移动一位，否则j回退到next[j]。

   在结束遍历后检查j指针指向位置，j指向子串最后一位加一，返回j-i，对应匹配起始位置，否则返回-1.