学习KMP && Sunday算法
引入
- Implement strStr()
- LeetCode实现String.indexOf(),即返回子串在字符串中第一次出现的索引位置,没有则返回-1,子串为空则返回0
- 暴力解法
- 从0位置开始,比对与子串是否相同,出现不同则在字符串中往后移一位,再次比较子串,直到找到。
- 复杂度
- 设字符串长度为m,要查找的子串长度为n
- 时间 O(m*n)
- 问题
- 每次出现不一致的情况,只向后移动一位,再从头开始比对,很多没有必要
- 如:在aaaaaaaaaaaab,查找aaaab
KMP
概念
- KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体位置,否则返回-1(常用手段)。
对于暴力破解的优化思考
- 主串不要每次只移一位,可以让它(i)保持不动,移动模式中j的位置
- 利用已经部分匹配这个有效信息,保持i指针不回溯,通过修改j指针,让模式串尽量地移动到有效的位置
- j要怎么移动
- 当匹配失败时,j要移动的下一个位置k。存在着这样的性质:最前面的k个字符和j之前的最后k个字符是一样的
数学表示
- 如果k表示不匹配时,j要移动的位置
P[0 ~ k-1] == P[j-k ~ j-1]
当T[i] != P[j]时
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然:T[i-k ~ i-1] == P[0 ~ k-1]
因此可以直接将j移动到k而无须再比较前面的k个字符
怎么找到不匹配时j要移动的k位置
- 模式串中每个位置发生不匹配时,所要移动到的k位置都是不同的,每个位置都要计算
- 使用next数据来保存模式串中每个位置的k值
- next[j]的值(也就是k)表示,当P[j] != T[i]时,j指针的下一步移动位置
当j为0时,如果这时候不匹配
j已经在最左边了,不可能再移动了,这时候要应该是i指针后移。有next[0] = -1
当j为1
j指针一定是后移到0位置的
其他
- 当P[k] == P[j]时
next[j+1] == next[j] + 1
P[k] != P[j]
k = next[k]
参考
代码实现
1 | class Solution { |
Sunday算法
1 | class Solution { |