{{docContent.title}}

(双指针,KMP)实现字符串定位

我的解法

像我这种菜鸡就喜欢用暴力的方法来求解,我这个方法实际上就是一个字符串一个字符串的比对,如果相同就进入循环一个一个字符串进行比对,如果比对完全匹配就返回匹配结果反之。

func strStr(haystack string, needle string) int {
	if needle == "" {
		return 0
	}
	// 字符串比对开始位置
	t := 0
        // 开始遍历haystack
	for i := 0; i < len(haystack); i++ {
                // 比对字符串,发现相同的就进入for循环
		if haystack[i] == needle[0] {
			t = i
                        // 循环needle,比对是否完全相同
			for j := 0; j < len(needle); j++ {
				if haystack[t] != needle[j] {
					break
				}
				t++
                                // 如果匹配到末尾就说明匹配成功
				if j == len(needle)-1 {
					return i
				}
                                // 这里我们判断t是否越界
				if t >= len(haystack) {
					return -1
				}
			}
		}
	}
	return -1
}

双指针

这里的双指针法其实已经说得很明显了,我们通过两个指针来分别定位原始字符串和查找的字符串,如果发现相同的字符串,那么就开始准备匹配,如果匹配过程中没有匹配完,那么就把指针重新置为刚开始匹配的那个字符串,如果匹配完毕,那么就直接返回位置

func strStr(haystack string, needle string) int {
	if needle == "" { //needle为空返回0
		return 0
	}
	if len(needle) > len(haystack) { //needle长度大于haystack返回-1
		return -1
	}
	var i, j int   //定义指针i,j分别对应haystack和needle
	var index = -1 //index位置初始值-1
	for i < len(haystack) && j < len(needle) {
		if haystack[i] == needle[j] { //如果当前指针处的字节相等
			if index == -1 { //index是初始值-1,则将当前i记录下来
				index = i
			}
			if j == len(needle)-1 { //如果当前的j已经是needle的最后一位,则返回index
				return index
			}
			j++ //否则needle的指针j往后移动一位
		} else { //当前指针处的字节不相等
			if index != -1 {
				i = index //如果index不为初始值-1,则将i赋值为index,下次从index的下一个位置开始继续找
				index = -1
				j = 0 //再将index和j赋值回初始值
			}
		}
		i++ //不管上面怎么变动,haystack的指针每次都要往后移动一位
	}
	return -1
}

KMP

KMP最难的地方就在于计算next数组,具体可以参考这篇文章。

https://www.cnblogs.com/SYCstudio/p/7194315.html

next数组的详解

func strStr(haystack string, needle string) int {
	// 获取两个字符串的长度
	n := len(haystack)
	m := len(needle)
	if m == 0 {
		return 0
	}
	if n < m {
		return -1
	}
	/*
		计算next数组 这个数组也叫匹配表数组(这个数组的长度就是haystck的长度)

		这里解释一下这个数组的意思 解释之前先理解一下前缀和后缀的概念
		前缀: 例如”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}
		后缀:例如,”Potter”的后缀包括{”r”,”er”,”ter”,”tter”,”otter”}
		这个两个其实一个是正过来一个个的往后加 后缀就是反过来的

		然后我们计算的这个表就是每位所包含的相同前后缀的最长的长度
		对于字符串”ababa”,它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”},它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}, 两个集合的交集为{”a”, ”aba”},其中最长的元素为”aba”,长度为3。
		我们拿ababa来举例 这个表有5位,第一为就是a的前后缀的最长长度 第二个就是ab 第三就是 aba 第四个是 abab 第五个是 ababa 就这样就算下去

	*/
	next := computeNext(needle)

	q := 0
	// 遍历字符串开始进行匹配
	for i := 0; i < n; i++ {
		// 如果不匹配,并且q不为0,那么我们就让q等于上一位的最短匹配长度
		for q > 0 && haystack[i] != needle[q] {
			q = next[q-1]
		}
		// 如果发现字符串匹配,那么就匹配下一位
		if haystack[i] == needle[q] {
			q++
		}
		// 如果发现q=m 就说明匹配完毕,我们这里计算一下匹配的位置
		if q == m {
			return i + 1 - m
		}
	}
	return -1
}

// 计算next的值
func computeNext(pattern string) []int {
	// 获取next里面的长度
	n := len(pattern)
	// 创建next数组
	next := make([]int, n)
	k := 0
	// 遍历字符串
	for q := 1; q < n; q++ {
		// 这里开始匹配k是从0开始,相当于计算前缀
		// q从1开始相当于计算后缀 这里默认就是开始匹配最长的前后缀
		// 如果不匹配那么最长的前缀就是上一个最长的前缀
		for k > 0 && (pattern[k] != pattern[q]) {
			k = next[k-1]
		}
		// 开始计算
		if pattern[k] == pattern[q] {
			k++
		}
		// 直接把第q为的值赋值进去
		next[q] = k
	}
	return next
}