// 思路1: 暴力BF算法, 每次从text的p开始和mode逐位比较, 如果不匹配, 就更新 p++;
public int strStr(String text, String mode) {
if(mode.length() == 0)
return 0;
//p指向主串开始比较的位置, j进行逐位比较的循环指针
int p = 0, j = -1;
// 剩余区间小于 mode长度就不必再匹配了
while(text.length() - p >= mode.length()){
j = p;
// 逐位比较成功直接返回p即可
for(int i =0 ;i < mode.length();){
if(text.charAt(j) == mode.charAt(i)){
if(i == mode.length() -1)
return p;
j++;
i++;
}else{
break;
}
}
// 如果失配了, 更新主串开始比较的指针为下一位
p++;
}
return -1;
}
Next数组
1、首先主串和模式串逐位比较, 如果匹配, 两个指针同时加1.
主串当前指针是 j , 模式串当前比较指针是i
2、而如果当前位置i 和 j 不匹配时, 模式串的比较指针i回退到模式串[0, i-1]之间的最长公共前后缀的长度的那个位置(即指向最长前缀的下一位), 此时再与主串的当前位置j继续进行比较. 如果还是不匹配, 重复2的过程. 直到回退到 i 和 j 匹配为止 或者 模式串比较指针i回退到了起始位置0.3、 发生不匹配后, 经过模式串指针的回退, 此时 主串和模式串又可以愉快的进行逐位的比较了, 匹配就走1 过程. 不匹配就走2 的过程. 如果模式串比较指针 j 匹配到了结尾代表匹配成功.整体失配匹配的过程
具体来看一次失配移动的过程
代码实现并不会真的去移动模式串, 所有的移动只是更新比较指针的位置而已
假设某主串 和 模式串 逐位比较到如下的情况, 假若此时 主串比较指针 i 和 模式串比较指针j发生不匹配. 如果按照暴力算法的思路, 此时主串比较指针j需要回退到主串索引1的位置, 模式串指针i需要回退到索引0到位置, 然后两者再继续从头开始逐位比较.
假设此时[0, i-1] 之间存在最长公共前后缀, 即ABA. 并且主串的最长公共前后缀是x1 和 x2, 模式串的最长公共前后缀是y1 和 y2, 并且x1 = x2( 是匹配的), y1 = y2, 并且由于[0, i-1] 和 [0, j-1] 是匹配的, 所以是不是有 x2 = y1 (是匹配的), 也就是说这部分y1和x2对于模式串和主串来说已经是匹配的就没有必要再继续进行匹配了, 所以我们只需要更新模式串的比较指针i到最长公共前后缀的长度的位置(即索引3的位置), 此时让它再去与主串的当前位置j继续进行比较即可, 如果匹配, 两个指针同时加1, 如果不匹配, 那么模式串指针i 同理继续回退.
最坏情况就是没有公共前后缀, 即模式串指针i 要回退到开头的位置从头去与主串的当前位置 j 继续比较. 所以即使这种最坏情况依旧比暴力匹配好, 因为主串比较指针并不用回退
直接更新模式串的指针i到最长公共前后缀的长度的位置到底会不会漏掉一些匹配的情况呢, 比如下图这种匹配情况
其实不会, 因为如果存在这种匹配情况,那么 x3 = y3(是匹配的), 而又因为 x3 和 y4在失配的时候本来就是匹配的, 所以最终导致 y3 = y4, 那么就说明应该此时会存在公共前后缀, 并且是最长的公共前后缀
1、主串的比较指针从来不用回退, 那么中间有没可能漏掉了一些匹配的情况?
2、 比如下图, 在G和F发生不匹配后因为没有公共前后缀, 模式串的比较指针 i 回退到了起始位置, 假设此时主串指针j 之前可能存在匹配的情况, 也就是如图可能会存在x2=y1(是匹配的)的这种情况, 但是其实这种情况是不可能发生的, 我们知道此时在位置j失配的情况下, x2 = y2(是匹配的). 所以如果存在x2=y1(是匹配的) , 那么 y1 和 y2 区域是匹配, 这不就是公共前后缀吗, 所以在没有公共前后缀的情况下, j之前的主串是没有与模式串前缀相匹配的, 所以主串指针j不用回退,直接从 j 开始继续比较即可.
斜着看, 更好理解为什么 x2 和 y1是匹配的, 这个的前提是基于我们之前的假设, 即此时主串指针j 之前可能存在匹配的情况(比如x2段)
我这里对于Next数组的定义是: next[i] 表示 next[0, i] 之间的最长公共前后缀的长度, 它代表的实际意义是指向最长前缀的下一位next数组理论计算过程
最长公共前后前后缀计算过程
实际上并不能肉眼就看出最长公共前后前后缀的长度是多少, 下面来看看具体如何去计算最长公共前后缀
原理
j 表示指向最长公共前缀的下一位(前缀指针), i表示指向最长公共后缀的下一位(后缀指针). 如果i 和 j 相等则前后缀指针同时+1, 如果不相等则需要回退前缀指针j 到上一个最长的前后缀长度的位置, 即 next[j-1]. 此时再比较j 和 i. 如果匹配则此时的j+1就是最长公共前后缀的长度. 如果还是不匹配则 前缀指针j 继续回退, 直到 j 和 i 相等或者 回退到起点0. 最后前缀指针 j + 1的值就表示next[0, i] 之间的最长前后缀的长度, 它意义也表示指向最长前缀的下一位
为什么 j 回退到next[j-1]就可以计算出最长的前后缀 ?
假设此时 前缀指针j 和 后缀指针计算到了如下情况, 在j=7和i=14时发生了失配. 而之前的最长前后缀是ABCDABC, 所以需要找到此时next[0, i] 之间的新的最长前后缀是什么.
这时我们 把 前缀指针 j 回退到 next[j-1]的位置 , 如下图. next[j-1] 就表示next[0, j-1]之间的最长前后缀的长度(即指向最长前缀的下一位), 此时最长前缀X0的子最长前后缀分别是x1 和 x2 区域, 同理最长后缀Y0的子最长前后缀就是y1 和 y2, 而又因为X0 和 Y0 是匹配的, 所以有 X1 和 y2 是匹配的
所以此时再去比较 j 和 i 的值就可以知道此时next[0, i] 之间的最长前后缀的长度. 如果相等最长公共前后缀的长度就是 j + 1, 如果还是不相等, 继续回退j 重复上述过程.
再次回退后, j 和 i 还是不想等, j 回退到0, 还是不想等. 所以next[i] = 0
def find(text, pattern) -> int:
"""
:param text: 主串
:param pattern: 模式串
:return:
"""
next: list = getNext(pattern)
# 模式串指针
j = 0
# 遍历主串和模式串逐位匹配
for i in range(len(text)):
# 如果发生失配， 则模式串指针j需要根据next数据回退
# 即回退到最长公共前缀的下一位， 即next[0,j-1]之间的最长公共前后缀的长度
# j 直到回退到0 或者 j 和 i 相等
while j > 0 and pattern[j] != text[i]:
j = next[j-1]
# 如果循环回退是因为j 和 i 相等退出，即模式串和主串当前位相等， 同时更新模式串指针j 和 主串指针i 即可
if pattern[j] == text[i]:
j += 1
# 如果遍历到了模式串的末尾， 索命模式串完全匹配成功， 返回它在主串的开始索引即可
if j == len(pattern):
return i - j + 1
return -1
def getNext(pattern: str) -> list:
""" 计算next数组 """
next: List[int] = [0] * len(pattern)
next[0] = 0 # 0位置最长公共前后缀长度一定是0，直接赋值即可
# 前缀指针
j = 0
# 计算每一个next[i], i同时表示后缀指针，不断+1， 不需要回退
for i in range(1, len(next)):
# 如果j 和 i不相等就一直回退， 直到相等或者 回退到起始位置
while j > 0 and pattern[j] != pattern[i]:
j = next[j-1]
# j 和 i 分别指向前后缀的最后一位， 如果相等则next[i]的最长公共前后缀长度就是 j+1
if pattern[j] == pattern[i]:
next[i] = j + 1
j += 1 # 更新前缀指针
return next
如果觉得文章有用,你可鼓励下作者
