串匹配 | 笔记整理!

串匹配 | 笔记整理!

串匹配

暴力匹配

概述

字符串暴力匹配是一种简单直接的匹配算法，也称为朴素匹配算法。它通过逐个字符地在主串中与模式串进行比较来找到匹配位置。

对于主串和匹配串进行暴力匹配，主串匹配时候索引会进行回溯！

字符串暴力匹配的时间复杂度为O(m*n)，其中m为主串的长度，n为模式串的长度。它是一种简单易懂的匹配算法，但对于较大规模的字符串匹配效率较低。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

func bruteForce(s,p string)int{
	m,n:=len(s),len(p)
	if n>m{
		return -1
	}
	for i:=0;i<m;i++{
		k:=i
		for j:=0;j<n;j++{
			if k<m&&s[k]==p[j]{
				k++
			}else{
				break
			}
		}
		if i+n==k{
			return i
		}
	}
	return -1
}

KMP匹配

概述

KMP（Knuth-Morris-Pratt）算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。它的核心思想是利用已经匹配过的信息来避免不必要的字符比较，从而提高匹配效率。

KMP算法的关键在于构建一个部分匹配表（Partial Match Table），也称为next数组。部分匹配表记录了模式串中每个位置之前的子串的最长相同前缀和后缀的长度。

下面是KMP算法的基本步骤：

1. 预处理模式串：根据模式串构建部分匹配表，即计算next数组。next[i]表示模式串中以第i个字符结尾的子串的最长相同前缀和后缀的长度。
2. 在主串中进行匹配：从主串的第一个字符开始，与模式串的第一个字符进行比较，如果相等，则比较下一个字符；如果不相等，则根据next数组移动模式串的指针。
3. 根据next数组移动模式串指针：如果当前字符不匹配，根据next数组找到模式串的一个新的起始位置，从该位置重新开始匹配。
4. 匹配成功：当模式串的指针移动到模式串的末尾时，表示匹配成功，返回主串中匹配开始的位置。

KMP算法通过预处理模式串构建部分匹配表，使得在匹配过程中避免了不必要的回溯，大大提高了匹配的效率。其时间复杂度为O(m+n)，其中m为主串的长度，n为模式串的长度。

过程推导

存在联系

1. 字符串匹配时候，可以不需要进行主串回溯，移动匹配串即可
2. 对于匹配串的移动是重点，观察字符串移动规律，不难得出前后缀关系

数理推导

next数组的推导是基于模式串自身的前缀和后缀的比较，可以使用递推的方式进行计算。

假设模式串为 p，next[i] 表示模式串中以第 i 个字符结尾的子串的最长相同前缀和后缀的长度。

1. 初始化 next[0] = 0，因为一个字符的字符串没有真前缀和真后缀。
2. 假设已知 next[0], next[1], ..., next[i-1] 的值，考虑如何求解 next[i]。
3. 当模式串的第 i 个字符与前一个字符匹配时，即 p[i] == p[next[i-1]]，可以扩展当前的相同前缀和后缀。
4. 如果模式串的第 i 个字符与前一个字符不匹配，即 p[i] != p[next[i-1]]，则需要回退到更短的相同前缀和后缀的位置继续比较。
5. 因此，我们可以通过递归地比较模式串的前缀和后缀，来确定 next[i] 的值。
   • 如果 p[i] == p[next[i-1]]，则 next[i] = next[i-1] + 1。
   • 如果 p[i] != p[next[i-1]]，则需要继续回退，即将 next[i-1] 的值作为新的位置进行比较，即 next[i] = next[next[i-1]]。
6. 重复步骤 3 和 4，直到找到一个匹配或回退到模式串的起始位置。
7. 根据上述推导，可以得到 next 数组的递推公式如下：
   • 如果 p[i] == p[next[i-1]]，则 next[i] = next[i-1] + 1。
   • 如果 p[i] != p[next[i-1]]，则 next[i] = next[next[i-1]]。

匹配优化：Nextval

概述

在KMP算法中，可以通过优化next数组来进一步提高匹配的效率。优化后的数组通常称为nextval数组。nextval数组的作用是在失配时跳过尽可能多的字符，减少不必要的比较。

下面是对nextval数组的优化过程：

1. 构建next数组：首先，根据模式串构建next数组，该数组表示模式串中每个位置之前的子串的最长相同前缀和后缀的长度。
2. 优化nextval数组：在next数组的基础上，根据模式串的前缀和后缀的关系，计算出nextval数组。
   • 初始化nextval数组，使每个元素等于对应位置的next数组的值。
   • 从右往左遍历nextval数组（从倒数第二个位置开始）：
     • 如果当前位置的nextval值大于0，则将当前位置的值更新为前一个位置的nextval值。
     • 如果当前位置的nextval值等于0，且当前位置的字符与前一个位置的字符相同，将当前位置的值更新为前一个位置的nextval值加1。
3. 在匹配过程中使用nextval数组：在主串与模式串进行匹配时，根据nextval数组的值进行指针的移动。
   • 如果当前字符不匹配，根据nextval数组找到模式串的一个新的起始位置，从该位置重新开始匹配。
   • 如果nextval数组中的值大于0，表示在失配时可以跳过尽可能多的字符，减少比较次数。

优化后的nextval数组使得在匹配过程中能够更有效地跳过不必要的字符比较，从而提高匹配的效率。

数理推导

nextval 数组是 KMP 算法中的一个优化，用于在失配时进行跳跃。假设模式串为 p，nextval[i] 表示当模式串第 i 个字符失配时，应该跳跃到的位置。

1. 初始化 nextval[0] = 0，表示模式串的第一个字符失配时跳跃到主串的下一个位置。
2. 假设已知 nextval[0], nextval[1], ..., nextval[i-1] 的值，考虑如何求解 nextval[i]。
3. 当模式串的第 i 个字符失配时，需要找到一个合适的跳跃位置。
4. 如果 p[i] == p[nextval[i-1]]，即当前失配的字符与前一个字符匹配，可以继续比较下一个字符，因此 nextval[i] = nextval[i-1] + 1。
5. 如果 p[i] != p[nextval[i-1]]，则需要回退到更短的相同前缀和后缀的位置继续比较。
6. 因此，我们可以通过递归地比较模式串的前缀和后缀，来确定 nextval[i] 的值。
   • 如果 p[i] == p[nextval[i-1]]，则 nextval[i] = nextval[i-1] + 1。
   • 如果 p[i] != p[nextval[i-1]]，则需要继续回退，即将 nextval[nextval[i-1]] 的值作为新的位置进行比较，即 nextval[i] = nextval[nextval[i-1]]。
7. 重复步骤 4 和 5，直到找到一个匹配或回退到模式串的起始位置。

代码风格

索引从0开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

func getNext(t string) []int {
	n := len(t)
	nxt := make([]int,n)
	nxt[0]=-1
	for i,j := 0, -1; i < n-1; {
		if j == -1 || t[i] == t[j] {
			i++
			j++
			nxt[i] = j
		} else {
			j = nxt[j]
		}
	}
	return nxt
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

func getNextval(t string)[]int{
	n := len(t)
	nxt := make([]int, n)
	nxt[0]=-1
	for j, i := -1, 0; i< n-1; {
		if j == -1 || t[i] == t[j] {
			i++
			j++
			if t[i]==t[j]{
				nxt[i]=nxt[j]
			}else{
				nxt[i] = j
			}
		} else {
			j = nxt[j]
		}
	}
	return nxt
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

func Kmp(s, t string) int {
	m, n := len(s), len(t)
	if n <= 0 {
		return 0
	}
	nxt := getNextval(t)
	i, j := 0, 0
	for i < m && j < n {
		if j == -1 || s[i] == t[j] {
			i++
			j++
		} else {
			j = nxt[j]
		}
		if j == n {
			return i - n
		}
	}
	return -1
}

索引从1开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func getNext(p string) []int {
	n := len(p)
	nxt := make([]int, n)
	for i, j := 1, 0; i < n-1; {
		if p[i] == p[j] || j == 0 {
			i++
			j++
			nxt[i] = j
		} else {
			j = nxt[j]
		}
	}
	return nxt
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func getNextval(p string) []int {
	n := len(p)
	nxt := make([]int, n)
	for i, j := 1, 0; i < n-1; {
		if p[i] == p[j] || j == 0 {
			i++
			j++
			if p[i] == p[j] {
				nxt[i] = nxt[j]
			} else {
				nxt[i] = j
			}
		} else {
			j = nxt[j]
		}
	}
	return nxt
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

func Kmp(s, p string) int {
	s = " " + s
	p = " " + p
	m, n := len(s), len(p)
	if n <= 0 {
		return 0
	}
	nxt := getNext(p)
	i, j := 0, 1
	for i < m && j < n {
		if j == 0 || s[i] == p[j] {
			i++
			j++
		} else {
			j = nxt[j]
		}
		if j == n {
			return i - n
		}
	}
	return -1
}

补充：字符串哈希

概述

字符串哈希（String Hashing）是一种将字符串映射为哈希值的技术。它可以将任意长度的字符串转换为固定长度的哈希码，方便在算法和数据结构中进行字符串的比较和查找操作。

字符串哈希的基本思想是将字符串看作是一个数字序列，通过对字符串中的字符进行一系列的运算和组合，得到一个哈希值。常用的字符串哈希算法包括简单的多项式哈希、Rabin-Karp哈希和Rolling哈希等。

以下是一种简单的多项式哈希算法的描述：

1. 选择一个合适的进制数（通常是一个素数），作为基数。例如，取素数31作为基数。
2. 将字符串中的每个字符转换为对应的数值，可以使用字符的ASCII码值。
3. 遍历字符串，对每个字符进行如下操作：
   • 将前一个字符的哈希值乘以基数，再加上当前字符的数值。
   • 这个步骤可以用以下公式表示：hash = hash * base + charValue。
4. 重复步骤3，直到遍历完整个字符串。
5. 最终得到的哈希值即为字符串的哈希码。

需要注意的是，字符串哈希可能存在哈希冲突，即不同的字符串可能得到相同的哈希值。为了尽量减少冲突的发生，通常会选择一个合适的基数和哈希算法。

字符串哈希在字符串匹配、查找和去重等场景中有广泛的应用。通过将字符串转换为哈希码，可以加速字符串的比较和查找操作，提高算法效率。